Algorithm Guidecomplexity: O(n)

Coin Change (Greedy)

A greedy strategy that always uses the largest coin first to make change. It's optimal when the denominations are multiples of one another (e.g. 500·100·50·10), but it doesn't guarantee the fewest coins for arbitrary denominations.

01Coin Change (Greedy)

Explore How It Works

Make change for 760. Greedily use the largest coin first.

500 ≤ 760 · use a 500 coin. Remaining amount 260.

100 ≤ 260 · use a 100 coin. Remaining amount 160.

100 ≤ 160 · use one more. Remaining amount 60.

100 > 60, so skip it and use a 50 coin. Remaining amount 10.

10 ≤ 10 · use the last 10 coin. Remaining amount 0.

Done · 760 made with 5 coins (500·100·100·50·10). For multiple-based denominations, greedy guarantees the fewest coins.

remaining760won

coins

500

100

picked · 0

Live Python

1def coin_change_greedy(coins, amount):

2 coins = sorted(coins, reverse=True)

3 result = []

4 for coin in coins:

5 while amount >= coin:

6 amount -= coin

7 result.append(coin)

8 return result if amount == 0 else None

1 / 7

02 Understand It Simply

For Everyone

🔑How It Works

Always takes the largest coin available. This is optimal only for canonical coin systems; otherwise it misses the optimal answer.

💡In Plain Words

Greedily picks the largest usable coin at every step.

With multiple-based denominations the fewest coins is guaranteed, but for arbitrary ones it can fail.

📍Where It's Used

–Making change
–allocating resources in fixed units

03 Python Implementation

A clean, readable reference implementation of the core logic of Coin Change (Greedy).

core_implementation.py

def coin_change_greedy(coins, amount):
    coins = sorted(coins, reverse=True)
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result if amount == 0 else None

04 Frequently Asked Questions

FAQ

What is Coin Change (Greedy)?+

What is the time complexity of Coin Change (Greedy)?+

The time complexity of Coin Change (Greedy) is O(n). Follow the step-by-step visualization to see exactly why.

Where is Coin Change (Greedy) used?+

Making change, allocating resources in fixed units.

What's a simple analogy for Coin Change (Greedy)?+

Always takes the largest coin available. This is optimal only for canonical coin systems; otherwise it misses the optimal answer.

→ Greedy — see allRelated