Coin change

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.

Exercise Greedy coin change

Write greedy_coins(coins, amount). Return the minimum coin count. Print 6 with print(greedy_coins([25, 10, 5, 1], 63)).

Show example 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))

Test yourself

Update remainder
```
amount ____ coin
```
Show answer
```
amount -= coin
```
Coin change: match the terms

coin

Coin
amount

Amount
remainder

Remainder
counter

Counter
How many coins does greedy give for 63 with [25,10,5,1]?
- 4
- 5
- 6
- 7
Show answer

6 — 6 (2×25 + 1×10 + 3×1).

Next lesson: Greedy limits

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies