Fewest coins to make an amount
You have an unlimited supply of coins of each denomination in coins. Return
the fewest coins that add up to amount, or -1 if it cannot be done.
Examples
| Input | Output | Why |
|---|---|---|
coins = [1, 5, 10, 25], amount = 30 | 2 | 25 + 5. |
coins = [1, 3, 4], amount = 6 | 2 | 3 + 3. Greedy would take 4 + 1 + 1 and use three. |
coins = [2], amount = 3 | -1 | Odd amounts are unreachable with a single even coin. |
Constraints
- 1 ≤ |coins| ≤ 12
- 1 ≤ coins[i] ≤ 2³¹ − 1
- 0 ≤ amount ≤ 10⁴
Hints
Hint 1
Try the greedy "take the largest coin that fits" on coins = [1, 3, 4] and amount = 6. It gives 3 coins; the answer is 2.
Hint 2
Write the recursion first: best(a) = 1 + min over coins c ≤ a of best(a − c), with best(0) = 0.
Hint 3
That recursion asks for the same amounts over and over. Fill an array from 0 upwards instead.
Dry run on [1,3,4],6
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 7best00∞1∞2∞3∞4∞5∞6coins1, 3, 4
best[0] = 0; every other amount starts at the sentinel 7, which stands for "unreachable".
-
Step 2 / 7best0011∞2∞3∞4∞5∞6amount1value1
best[1] = 1, taking coin 1 and reading the already-final best[0] = 0.
-
Step 3 / 7best001122∞3∞4∞5∞6amount2value2
best[2] = 2, taking coin 1 and reading the already-final best[1] = 1.
-
Step 4 / 7best00112213∞4∞5∞6amount3value1
best[3] = 1, taking coin 3 and reading the already-final best[0] = 0.
-
Step 5 / 7best0011221314∞5∞6amount4value1
best[4] = 1, taking coin 4 and reading the already-final best[0] = 0.
-
Step 6 / 7best001122131425∞6amount5value2
best[5] = 2, taking coin 1 and reading the already-final best[4] = 1.
-
Step 7 / 7best00112213142526amount6value2
best[6] = 2, taking coin 3 and reading the already-final best[3] = 1.
How to think about it
Greedy is wrong here, and the counterexample is worth keeping: with coins 1, 3, 4 and amount 6, taking the largest coin first gives 4 + 1 + 1, while 3 + 3 is better. Greedy only works for special coin systems, which is exactly the kind of assumption an interviewer wants you to question out loud.
The honest formulation is a recursion: the best way to make a is one coin
c plus the best way to make a − c, minimised over the coins that fit.
Written recursively it recomputes the same amounts endlessly. Written as a loop from 0 up to the
target, each amount is solved once and read many times:
best[0] = 0
best[a] = 1 + min(best[a - c]) over coins c ≤ aThat is O(amount × |coins|) time and O(amount) space. The order matters: by the time you compute
best[a], every smaller amount is already final, which is what lets you read them
without recursion. Use a sentinel such as amount + 1 for "unreachable" so the
minimum works without special cases.
Complexity. Time O(amount × |coins|) · Space O(amount)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def coin_change(coins, amount):
INF = amount + 1 # a value no real answer can reach
best = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a and best[a - c] + 1 < best[a]:
best[a] = best[a - c] + 1
return -1 if best[amount] == INF else best[amount]#include <vector>
int solve(const std::vector<int>& coins, int amount) {
const int INF = amount + 1; // never a real answer
std::vector<int> best(amount + 1, INF);
best[0] = 0;
for (int a = 1; a <= amount; ++a)
for (int c : coins)
if (c <= a && best[a - c] + 1 < best[a])
best[a] = best[a - c] + 1;
return best[amount] == INF ? -1 : best[amount];
}class Solution {
public int coinChange(int[] coins, int amount) {
final int INF = amount + 1;
int[] best = new int[amount + 1];
java.util.Arrays.fill(best, INF);
best[0] = 0;
for (int a = 1; a <= amount; a++)
for (int c : coins)
if (c <= a && best[a - c] + 1 < best[a])
best[a] = best[a - c] + 1;
return best[amount] == INF ? -1 : best[amount];
}
}function coinChange(coins, amount) {
const INF = amount + 1; // a value no real answer can reach
const best = new Array(amount + 1).fill(INF);
best[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const c of coins) {
if (c <= a && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 1;
}
}
return best[amount] === INF ? -1 : best[amount];
}fn solve(coins: &[usize], amount: usize) -> i64 {
let inf = amount + 1; // never a real answer
let mut best = vec![inf; amount + 1];
best[0] = 0;
for a in 1..=amount {
for &c in coins {
if c <= a && best[a - c] + 1 < best[a] {
best[a] = best[a - c] + 1;
}
}
}
if best[amount] == inf { -1 } else { best[amount] as i64 }
}import Data.Array
-- A lazy array is the idiomatic table: each entry refers to earlier entries.
solve :: [Int] -> Int -> Int
solve coins amount = if best ! amount == inf then -1 else best ! amount
where
inf = amount + 1
best = listArray (0, amount) [f a | a <- [0 .. amount]]
f 0 = 0
f a = minimum (inf : [best ! (a - c) + 1 | c <- coins, c <= a, best ! (a - c) < inf])Where people lose marks
- Reaching for greedy without testing it. State the counterexample before writing code.
- Using infinity as the sentinel and then adding 1 to it: in fixed-width integers that overflows. Use
amount + 1. - Forgetting amount = 0, which must return 0.
Variants to try
- Count the number of ways instead of the fewest coins: loop over coins on the outside to avoid counting permutations twice.
- Return the actual coins: keep the coin that achieved each amount and walk back.
- Very large amounts with few coins: this becomes a shortest-path or number-theoretic problem, not a table.
Next problems
Write a solution and run it against the real test table.
Keep going
Largest sum with no two chosen positions adjacent
Two states, one recurrence, O(1) memory. The example to reach for when someone asks you to explain dynamic programming.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.