coins, and every denomination is a power of two. You need to pay exactly amount by picking some of the coins, with no change given.
In one operation you may break a coin worth more than 1 into two coins of half its value.
Return the fewest breaks after which some coins in the wallet add up to exactly amount. If that is impossible, return -1.coins=[1, 4], amount=3 → 1
Break the 4 into two 2s and pay 1 + 2 = 3. One break is enough.
coins=[16], amount=3 → 4
16 → 8 + 8, then 8 → 4 + 4, 4 → 2 + 2 and 2 → 1 + 1. After four breaks you hold a 2 and a 1.
coins=[2, 2], amount=5 → -1
There is only 4 in total and breaking coins never changes the total.
len(coins) ≤ 1000coins[i] ≤ 2³⁰, and coins[i] is a power of twoamount < 2³¹coins=[1, 4], amount=3
1
Run checks the first 3 tests in your browser. Submit checks all 118 tests on the server, hidden ones included.