Greedy Coin Change Visualizer: Minimum Coins

Animate the greedy coin change algorithm. Watch how picking the largest coin at every step finds the minimum number of coins for canonical systems.

Greedy Coin Change: how it works

Greedy vs DP
Greedy always picks the largest coin ≤ remaining. This gives the minimum coins for "canonical" systems (US coins, Euro). For arbitrary denominations (e.g. [1,3,4], amount=6) greedy can fail, so use DP instead.
Algorithm
Sort denominations descending. For each denomination, greedily take as many coins as possible (remaining ÷ denom). Update remaining and repeat.
Example: 36¢
36 ÷ 25 = 1 → use 25¢ (remaining=11). 11 ÷ 10 = 1 → use 10¢ (remaining=1). 1 ÷ 5 = 0 → skip. 1 ÷ 1 = 1 → use 1¢. Total: 3 coins.
When greedy fails
Denominations [1,3,4], amount=6: greedy picks 4+1+1=3 coins. DP finds 3+3=2 coins. The greedy choice (largest coin) is not always locally optimal for arbitrary systems.

Animate the greedy coin change algorithm. Watch how picking the largest coin at every step finds the minimum number of coins for canonical systems.

Greedy vs DP
Greedy always picks the largest coin ≤ remaining. This gives the minimum coins for "canonical" systems (US coins, Euro). For arbitrary denominations (e.g. [1,3,4], amount=6) greedy can fail, so use DP instead.
Algorithm
Sort denominations descending. For each denomination, greedily take as many coins as possible (remaining ÷ denom). Update remaining and repeat.
Example: 36¢
36 ÷ 25 = 1 → use 25¢ (remaining=11). 11 ÷ 10 = 1 → use 10¢ (remaining=1). 1 ÷ 5 = 0 → skip. 1 ÷ 1 = 1 → use 1¢. Total: 3 coins.
When greedy fails
Denominations [1,3,4], amount=6: greedy picks 4+1+1=3 coins. DP finds 3+3=2 coins. The greedy choice (largest coin) is not always locally optimal for arbitrary systems.