coins. Each coin can be used at most once in a payment.
You want every amount from 1 to limit inclusive to be payable exactly, using some set of coins from the wallet. To get there, you may add new coins of any value to the wallet.
Return the minimum number of coins you need to add.coins=[1, 4], limit=7 → 1
Right now only 1, 4 and 5 can be paid. Adding a coin of 2 makes every amount from 1 to 7 payable.
coins=[2, 3], limit=10 → 2
Without a coin of 1 the amount 1 is unreachable, so add it. Coins 1, 2, 3 cover everything up to 6; one more coin, say 7, extends that to 13 ≥ 10.
coins=[1, 1, 3], limit=5 → 0
The coins already cover every amount from 1 to 5, so nothing needs to be added.
coins is sorted in non-decreasing ordercoins=[1, 4], limit=7
1
Run checks the first 3 tests in your browser. Submit checks all 100 tests on the server, hidden ones included.