coins[i] is the value of the i-th coin. Each coin may be used at most once. A sum is reachable if some subset of the coins adds up to it.
You may put new coins of any value into the wallet. Return the minimum number of coins you have to add so that every sum from 1 to limit inclusive becomes reachable.coins=[1, 3, 9], limit=14 → 2
Add a 2: with 1, 2, 3 every sum up to 6 works. Then 7 and 8 are still missing, so add a 7: with 1, 2, 3, 7, 9 everything up to 22 is reachable. Total 2.
coins=[1, 2, 4], limit=7 → 0
1, 2 and 4 already make every sum from 1 to 7.
coins=[5], limit=5 → 3
coins=[1, 3, 9], limit=14
2
Run checks the first 3 tests in your browser. Submit checks all 112 tests on the server, hidden ones included.