coins, номинал каждой — степень двойки. Нужно заплатить ровно amount, выбрав некоторые из монет без сдачи.
За одну операцию можно разменять монету номиналом больше 1 на две монеты вдвое меньшего номинала.
Верните наименьшее число разменов, после которых из кошелька можно выбрать монеты на сумму ровно amount. Если это невозможно, верните -1.coins=[1, 4], amount=3 → 1
Размениваем 4 на две монеты по 2 и платим 1 + 2 = 3. Одного размена достаточно.
coins=[16], amount=3 → 4
16 → 8 + 8, затем 8 → 4 + 4, 4 → 2 + 2, 2 → 1 + 1. После четырёх разменов есть монеты 2 и 1.
coins=[2, 2], amount=5 → -1
Всего денег 4, а нужно 5 — размены сумму не меняют.
len(coins) ≤ 1000coins[i] ≤ 2³⁰, и coins[i] — степень двойкиamount < 2³¹coins=[1, 4], amount=3
1
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 118 тестов на сервере, включая скрытые.