Coin Change
You get a list coins of different coin values and a target amount. You may use each coin value as many times as you want. Return the smallest number of coins whose values add up to exactly amount, or -1 if no mix of coins reaches it. An amount of 0 needs 0 coins.
Function
- coinsinteger-array
- the different coin values, each usable any number of times
- amountinteger
- the total to pay exactly
- Returnsinteger
- the fewest coins needed, or -1 when the amount cannot be made
Constraints
1 ≤ coins.length ≤ 121 ≤ coins[i] ≤ 1040 ≤ amount ≤ 104- All coin values are different.
Examples
- Input
- coins = [2, 5, 10]amount = 27
- Output
- 4
- Explanation
- 10 + 10 + 5 + 2 makes 27 with four coins. Three coins fail: 27 is odd, so they need exactly one 5, and the other two add at most 20, short of 22.
- Input
- coins = [4, 6]amount = 7
- Output
- -1
- Explanation
- Both coin values are even, so every total you can build is even. 7 is odd, so the answer is -1.
- Input
- coins = [3, 7]amount = 0
- Output
- 0
- Explanation
- Paying 0 takes no coins at all, so the answer is 0 whatever the coin values are.
Follow-up
Can you count how many different combinations of coins add up to amount, instead of finding the fewest coins?
Hints
Open them one at a time. Each one gives away a little more.
Always taking the largest coin that fits does not always give the fewest coins. Try it on coins
[1, 3, 4]and amount6.Suppose you already knew the fewest coins for every amount smaller than
t. Which smaller amounts cantbe reached from with one more coin?Fill a table
fewest[0..amount]from0upwards:fewest[0] = 0, and eachfewest[t]is one more than the bestfewest[t - c]over the coinsc <= t. Mark amounts nobody can reach with a value larger than any real answer, such asamount + 1, and turn it into-1at the end.
Solution
Taking the largest coin that fits fails: with coins 1, 3 and 4 it pays 6 as 4 + 1 + 1, while 3 + 3 needs two coins. The fewest coins for an amount depends only on the fewest coins for smaller amounts, so you solve each amount from 0 to amount once.
Try every combination with recursion
Correct, but does not finish on the largest tests
Intuition
If the last coin you pay is worth c, the coins before it pay remaining - c as cheaply as possible. So fewest(remaining) is one more than the best fewest(remaining - c) over every coin that fits. This tries every sequence of coins that does not overshoot, so it cannot miss the best one.
It solves the same amounts again and again. With coins 2, 5 and 10, amount 27 reaches 15 after paying 10 + 2, 2 + 10, 5 + 5 + 2 and more orders, and works out 15 from scratch each time. The number of calls grows exponentially with the amount.
Algorithm
- Write a helper
fewest(remaining)that returns the fewest coins forremaining, or -1 if none work. - If
remainingis 0, return 0. - For every coin not larger than
remaining, call the helper on what is left after paying that coin. - Keep the smallest result that is not -1, plus one for the coin you paid.
- Return that count, or -1 if every coin led nowhere. The answer is
fewest(amount).
def coinChange(coins, amount):
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
return best
return fewest(amount)Recursion with memoization
Correct, but does not finish on the largest tests
Intuition
The recursion only asks about amounts from 0 to amount. Store each answer in an array the first time you work it out, and return the stored value when that amount comes up again. Each amount is solved once with a loop over the coins: O(amount × coins) work.
The calls still nest one level per coin paid. With a coin worth 1 that is up to 10^4 levels, more than the default call stack allows in many languages.
Algorithm
- Make an array
memowith room for every amount from 0 toamount, holding a marker that means not worked out yet. - In
fewest(remaining), return 0 for 0, and returnmemo[remaining]if it already holds an answer. - Otherwise try every coin that fits, as in the plain recursion, and keep the smallest result plus one.
- Save the result, -1 included, in
memo[remaining]before you return it. - Return
fewest(amount).
def coinChange(coins, amount):
# memo[r] holds the answer for r once it is worked out; None means not yet
memo = [None] * (amount + 1)
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
if memo[remaining] is not None:
return memo[remaining]
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
memo[remaining] = best
return best
return fewest(amount)Bottom-up dynamic programming over amounts
Intuition
Fill a table fewest from 0 upwards. When you reach a total t, every smaller total is settled, so fewest[t] is one more than the smallest fewest[t-c] over the coins c that fit.
Totals that no mix of coins reaches hold the marker amount + 1. Every coin is worth at least 1, so a real answer never uses more than amount coins, and the marker loses every comparison. A loop replaces the recursion, so the depth of the call stack never matters.
Algorithm
- Make
fewestwithamount + 1entries, all set to the markeramount + 1, and setfewest[0]to 0. - For each total
tfrom 1 toamount, look at every coincwithc ≤ t. - If
fewest[t-c] + 1is smaller thanfewest[t], store it infewest[t]. - After the loop, return -1 if
fewest[amount]still holds the marker, andfewest[amount]otherwise.
def coinChange(coins, amount):
impossible = amount + 1
fewest = [0] + [impossible] * amount
for total in range(1, amount + 1):
for coin in coins:
if coin <= total and fewest[total - coin] + 1 < fewest[total]:
fewest[total] = fewest[total - coin] + 1
return fewest[amount] if fewest[amount] != impossible else -1
Pitfalls and edge cases
- Taking the largest coin first. With coins 3 and 5 and amount 9 it pays 5 and 3, gets stuck at 1 and returns -1, while 3 + 3 + 3 works.
- Using the largest integer as the marker. Adding 1 to it overflows to a negative number, which then wins every comparison. Use
amount + 1. - Adding 1 to a dead end. A branch that returns -1, plus the coin you paid, gives 0 and wins every comparison. Skip -1 results.
- Recursing
amountlevels deep. With a coin worth 1 and amount10^4, Python stops at its default 1000 levels, and JavaScript, Dart, Ruby and R run out of stack too. - Reading
fewest[t-c]for a coin larger thant, before the start of the table.
Frequently asked questions3
Why does the greedy approach fail for Coin Change?
Taking the largest coin that fits is safe only for some coin systems, such as most real currencies. With coins 1, 3 and 4 it pays 6 with three coins instead of two, and with coins 3 and 5 it cannot pay 9 at all. Dynamic programming compares every choice, so no coin system fools it.
What is the time complexity of Coin Change?
The dynamic programming solution takes O(amount × coins) time and O(amount) space: one table entry per amount, and every coin checked for each entry. Plain recursion without memoization is exponential in the amount.
Is top-down or bottom-up better for Coin Change?
Both do the same O(amount × coins) work. Top-down recursion can nest as deep as the amount, which overflows the call stack for 10^4 in several languages. Bottom-up fills the table with a loop, so it has no depth limit and is the safer choice in an interview.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def coinChange(coins, amount):
# Write code hereTest #1
Test #2
Test #3
Arguments
coins = [2, 5, 10] amount = 27
Expected Output
4