Greedy Denomination Coins

Description

Make an amount with the fewest coins and notes. For everyday currencies, "take the biggest note that fits, repeat" is exactly right - but it's a property of the particular denominations, not of the method, and it's easy to apply where it quietly fails.

This skill covers largest-first change done with division, how to recognize the coin sets where it is safe, and the limited-supply version where even a familiar currency can trap it. When greedy isn't safe, the fallback is dynamic programming.

We'll go from simple to more technical:

1. The pattern: largest denomination first, taking as many as fit with one division.
2. A second flavor: limited supply (Lemonade Change, an ATM) and keeping the flexible coins.
3. Where largest-first shows up (cash registers, dispensers, formatting durations and sizes).
4. What breaks it: non-canonical coin sets, limited stock, subtracting one coin at a time.

The approach

int minCoins(int amount) {
    int[] denominations = {200, 100, 50, 20, 10, 5, 2, 1};   // euros, largest first
    int count = 0;
    for (int d : denominations) {
        count += amount / d;       // as many of this note as fit
        amount %= d;
    }
    return count;
}

def min_coins(amount: int) -> int:
    count = 0
    for d in [200, 100, 50, 20, 10, 5, 2, 1]:   # euros, largest first
        used, amount = divmod(amount, d)             # as many of this note as fit
        count += used
    return count

Using division instead of subtracting one note at a time keeps it O(number of denominations) even for 10^9 (5,000,000 notes of 200 euros). The euro set is canonical: greedy matches the true minimum for every amount - checked by DP for every amount up to 5,000, far past the point where a counterexample would have to appear. So are 1, 5, 10, 25. But with coins 1, 3 and 4, greedy pays 6 as 4 + 1 + 1 (three coins) instead of 3 + 3 (two). For an arbitrary set, the fewest-coins problem needs dynamic programming.

A second flavor: limited supply

A till or an ATM doesn't have unlimited notes, and then even a canonical system can trap greedy. Lemonade costs 5; customers pay with 5, 10 or 20, in order, and you start with no change:

boolean lemonadeChange(int[] bills) {
    int fives = 0, tens = 0;
    for (int b : bills) {
        if (b == 5) {
            fives++;
        } else if (b == 10) {
            if (fives == 0) return false;
            fives--;
            tens++;
        } else {                                              // 20 needs 15 back
            if (tens > 0 && fives > 0) { tens--; fives--; }   // prefer 10 + 5: fives are needed for every change
            else if (fives >= 3) fives -= 3;
            else return false;
        }
    }
    return true;
}

def lemonade_change(bills: list[int]) -> bool:
    fives = tens = 0
    for b in bills:
        if b == 5:
            fives += 1
        elif b == 10:
            if fives == 0:
                return False
            fives -= 1
            tens += 1
        else:                                        # 20 needs 15 back
            if tens > 0 and fives > 0:               # prefer 10 + 5: fives are needed for every change
                tens -= 1
                fives -= 1
            elif fives >= 3:
                fives -= 3
            else:
                return False
    return True

Fives can make any change and tens can't, so spend a ten when you can. Paying 15 as three fives first fails on 5, 5, 5, 5, 10, 20, 10: after the 20, no five is left for the final 10. The same trap hits an ATM: to pay 60 holding one 50 and three 20s, "largest first" takes the 50 and then can't make 10, while 20 + 20 + 20 works.

Where you'll see it

Cash registers and change calculators use greedy because national currencies are designed to be canonical. Dispensers with a limited stock of each note need to check feasibility (or search) rather than trust plain greedy. The same "largest unit first" formats durations ("1h 2m 5s") and file sizes.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why does greedy make 6 badly with coins 1, 3 and 4?

2. In Lemonade Change, why give 10 + 5 for a 20 rather than 5 + 5 + 5?

3. Why compute amount / d instead of subtracting d repeatedly?

Key takeaways

• Largest-first change is optimal only for canonical denominations; check with DP below the two largest coins' sum.
• For arbitrary denominations, fewest coins is DP.
• With limited supply, greedy can fail even for canonical systems - keep flexible coins.
• Divide, don't subtract one coin at a time.