Coin change, and why greedy is wrong

Interview QuestionsBy Ashish JangraUpdated 15 September 2026

Take the biggest coin first and you get the wrong answer: with [1, 3, 4] for 6, greedy picks 4+1+1 — three coins — where 3+3 is two. The fix is a table: best[a] = 1 + min(best[a - c]) over the coins that fit, in O(amount × coins).

Overview

The question, and what it is testing

Dynamic programmingCoding problemMedium

Step through it

What to watch

Every entry is built from a smaller amount, which is why filling upwards works.
Greedy commits to the 4 and cannot undo it.
Unreachable amounts stay at infinity and become −1.

Say this out loud

"Greedy does not work in general - with coins 1, 3, 4 and amount 6 it gives three coins where two is optimal. So a table: best[a] is one plus the minimum over best[a - c] for each coin c that fits, filled upwards from 0. O(amount times number of coins) time, O(amount) space. Greedy happens to be optimal for canonical systems like real currency, which is why the intuition is so strong."

def greedy(coins, amount): """Biggest coin first. Correct for some systems, not in general.""" used, left = [], amount for c in sorted(coins, reverse=True): while left >= c: left -= c used.append(c) return used if left == 0 else None def fewest(coins, amount): """best[a] = 1 + min(best[a - c]) over coins that fit.""" INF = float("inf") best = [0] + [INF] * amount pick = [None] * (amount + 1) # for reconstructing the coins 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 pick[a] = c if best[amount] == INF: return -1, [] coins_used, a = [], amount while a > 0: coins_used.append(pick[a]) a -= pick[a] return int(best[amount]), sorted(coins_used) coins, amount = [1, 3, 4], 6 g = greedy(coins, amount) n, used = fewest(coins, amount) print(f"coins {coins} amount {amount}") print(f" greedy : {g} -> {len(g)} coins") print(f" optimal: {used} -> {n} coins") print(" greedy loses because it commits to the 4 and cannot undo it")

def greedy(coins, amount): used, left = [], amount for c in sorted(coins, reverse=True): while left >= c: left -= c used.append(c) return used if left == 0 else None def fewest(coins, amount): INF = float("inf") best = [0] + [INF] * amount pick = [None] * (amount + 1) 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 pick[a] = c if best[amount] == INF: return -1, [] coins_used, a = [], amount while a > 0: coins_used.append(pick[a]) a -= pick[a] return int(best[amount]), sorted(coins_used) # Greedy IS optimal for canonical systems - which is why the intuition sticks. print() print("real currency [1, 5, 10, 25]:") agree = True for amt in range(1, 100): gg = greedy([1, 5, 10, 25], amt) dd, _ = fewest([1, 5, 10, 25], amt) if len(gg) != dd: agree = False print(f" disagree at {amt}: greedy {len(gg)}, optimal {dd}") print(" greedy matches the optimum for every amount 1..99:", agree)

def greedy(coins, amount): used, left = [], amount for c in sorted(coins, reverse=True): while left >= c: left -= c used.append(c) return used if left == 0 else None def fewest(coins, amount): INF = float("inf") best = [0] + [INF] * amount pick = [None] * (amount + 1) 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 pick[a] = c if best[amount] == INF: return -1, [] coins_used, a = [], amount while a > 0: coins_used.append(pick[a]) a -= pick[a] return int(best[amount]), sorted(coins_used) # The edges. print() print("amount 0 needs no coins:", fewest([1, 2, 5], 0)) print("unreachable amounts give -1:", fewest([5, 10], 3)) print("a single coin that fits exactly:", fewest([7], 7)) # Cost, and the word that matters. amount = 5_000 n, _ = fewest([1, 3, 4], amount) print() print(f"amount {amount:,} with 3 coins -> {n} coins") print(f" table entries filled: {amount:,} (amount x coins operations)") print(" note 'amount' is a VALUE, not a length: this is pseudo-polynomial")