Pay an amount with the fewest coins
Reported in interviews at (where)
A country has coins of n different values, and you have as many of each as you like. For each test, find the fewest coins that add up to exactly amount, or -1 if no set of coins does.
Always taking the biggest coin that fits does not always give the fewest coins.
Input
The first line holds T, the number of tests. Each test is two lines: n and amount, then the n coin values.
Output
For each test, one line: the fewest coins that make its amount, or -1.
- Input
4
3 6
1 3 4
1 7
2
2 0
5 9
3 11
1 5 6- Output
2
-1
0
2
- Taking the biggest coin first gives 4 + 1 + 1, three coins, but 3 + 3 uses two.
- Coins of 2 only make even amounts.
- An amount of 0 needs no coins.
- 5 + 6.
Limits
1 <= T <= 1001 <= n <= 50, and the n coin values differ1 <= each coin value <= 100000 <= amount <= 10000n times amount, added over all the tests, is at most 4000000
Hints
Hint 1
Work out the answer for every amount from 0 up: the fewest coins for v is one more than the fewest for v - c, for the best coin c.
Hint 2
Keep a table best[0..amount] with best[0] = 0 and every other amount "impossible" to start; fill it upwards. That is O(n * amount).
Where this was reported
- JPMorgan Chase, Software engineer programme HireVue, 2019 (GeeksforGeeks)
- PayPal, On-campus internship interview, 2015 (GeeksforGeeks)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
