A vending machine has unlimited coins of each value in coins (all positive, no duplicates). Write a function that returns the fewest coins that add up to exactly amount, or -1 if it can't be done. An amount of 0 needs 0 coins.
text
1fewest_coins([1, 3, 4], 6) -> 2
2fewest_coins([5, 10], 3) -> -1
3fewest_coins([2], 0) -> 0
In the first example, 3 + 3 uses two coins. Taking the biggest coin first (4 + 1 + 1) uses three.
Write fewest_coins(coins, amount) in Python or fewestCoins(coins, amount) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 22 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Greedy doesn't work
Always taking the largest coin that fits works for some coin systems, but not all, as the first example shows. You need to consider every option.
Step 2
Define the state
Let best[a] be the fewest coins that make amount a. The answer is best[amount].
Step 3
The recurrence
The last coin used to make a is one of the coins c (with c <= a). After removing it, you need best[a - c] more. So best[a] = 1 + min(best[a - c]) over every coin c that fits. If no coin leads anywhere reachable, a can't be made.
best[0] = 0. Fill best[1], best[2], ... in order, so every smaller amount is ready when you need it. Use "infinity" for amounts that can't be made, and turn it into -1 at the very end.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Create best of size amount + 1, filled with infinity, and set best[0] = 0. For each amount from 1 up, try each coin that fits and keep best[a - c] + 1 if it's smaller. Return best[amount], or -1 if it's still infinity.
python
1def fewest_coins(coins, amount):
2 impossible = float("inf")
3 best = [0] + [impossible] * amount # best[a] = fewest coins that make a
↑best[a] = fewest coins for amount a
4 for a in range(1, amount + 1):
↑small amounts first
5 for c in coins:
6 if c <= a and best[a - c] + 1 < best[a]:
↑use coin c last: 1 + best[a − c]
7 best[a] = best[a - c] + 1
8 return -1 if best[amount] == impossible else best[amount]
↑never reached: impossible
javascript
1function fewestCoins(coins, amount) {
2 const best = new Array(amount + 1).fill(Infinity) // best[a] = fewest coins that make a
↑best[a] = fewest coins for amount a
3 best[0] = 0
4 for (let a = 1; a <= amount; a++) {
↑small amounts first
5 for (const c of coins) {
6 if (c <= a && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 1