Coin change
- Algorithms course
- Intermediate
- Lesson 62/80
- 4 min
Greedy coin change example.
Coin change
Greedy coin change: given denominations, pay an amount with as few coins as possible. Take the largest coin each step.
With standard systems like 1, 5, 10, 25 greedy gives the optimum; otherwise DP is needed.
That is why real coin change machines use greedy; fast and optimal on standard systems.
Step by step
Each iteration subtracts the largest coin from the remainder and increments the counter. Stop when the remainder is zero.
This is the classic greedy loop; one coin is taken per step.
The loop runs until the remainder hits zero; all coins are processed in turn.
Practice Greedy coin change
Write greedy_coins(coins, amount). Return the minimum coin count. Print 6 with print(greedy_coins([25, 10, 5, 1], 63)).
Starter code
def greedy_coins(coins, amount):
# Minimum coin countSample solution
def greedy_coins(coins, amount):
# Minimum coin count
coins.sort(reverse=True)
count = 0
for coin in coins:
count += amount // coin
amount = amount % coin
return count
print(greedy_coins([25, 10, 5, 1], 63))Expected output
6
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Update remainder
amount ____ coinamount -= coinExplanation: -= is right.
2 Coin change: match the terms
| Term | Meaning |
|---|---|
coin |
Coin |
amount |
Amount |
remainder |
Remainder |
counter |
Counter |
3 How many coins does greedy give for 63 with [25,10,5,1]?
- 4
- 5
- 6 Correct answer
- 7
Explanation: 6 (2×25 + 1×10 + 3×1).