Making change
Take as many of the largest coin as possible before moving to smaller denominations. About 7 minutes.
Biggest coin first
With Indian coins of 20, 10, 5, 2 and 1, always take as many of the biggest coin as fit, then move to the next. These coins are designed so that biggest-first always gives the fewest coins.
Dividing rather than subtracting one coin at a time means even a billion rupees takes only five steps.
count = 0
for d in (20, 10, 5, 2, 1):
count += amount // d
amount %= d
return count- owed
- 7
- coins
- 3
₹20: 67 divided by 20, rounded down, is 3, so 3 coins fit. That covers 60, so ₹7 is still owed.
Greedy isn't always right
With made-up coins of 1, 3 and 4, and an amount of 6, biggest-first takes 4 + 1 + 1, which is 3 coins. But 3 + 3 uses only 2.
Greedy is safe here only because real coin systems are designed so that it works. Later, dynamic programming handles any coin set.
How many coins does biggest-first hand over for ₹38 with coins [20, 10, 5, 2, 1]?
- A5 coins
- B4 coins
- C6 coins
Show the answer
5 coins. 20 leaves 18, 10 leaves 8, 5 leaves 3, 2 leaves 1, 1 leaves 0: five coins.
Making change
A shopkeeper owes you amount rupees and has plenty of ₹20, ₹10, ₹5, ₹2 and ₹1 coins. Return the fewest coins that add up to exactly amount.
amount = 67 → 5
0 ≤ amount ≤ 1,000,000,000