Coin Change (Greedy)Making change

01Why it exists

Reach for it when you see:Making change, fewest coins, largest denomination first, canonical coin systems, switching to DP when greedy fails.

02The core idea

The greedy solution to making change has exactly one rule: go from the largest denomination down, taking as many of each as the remaining amount allows. The implementation is a single loop with one integer division and one remainder per denomination, so it is O(k) for k denominations. It never looks at any other combination, which makes it almost free.

It is correct for a system like [1, 5, 10, 50], and the intuition is this: in any optimal solution, the number of small coins is capped (at most four 1s, at most one 5, at most four 10s), because going over the cap would let you swap them for a larger coin and use fewer. Those caps together cannot reach the next larger denomination, so as long as the remaining amount is big enough, the optimal solution must contain that larger coin — and taking it greedily cannot be wrong. That is the exchange argument: swap "several small coins" in an optimal solution for "one large coin" and the count only goes down.

Greedy is wrong for [1, 3, 4] at 6: take the 4, and the remaining 2 can only be two 1s, three coins in all, where 3+3 needs only two. The exchange argument fails here because two 3s cannot be swapped for a single larger coin. A system like this is called non-canonical. To decide whether a set of denominations is canonical, Kozen and Zaks proved that the smallest counterexample is always below the sum of the two largest denominations, so comparing greedy against DP over that range settles it — no infinite check required.

When greedy is wrong, the correct solution is DP: dp[a] = min(dp[a − c] + 1) over every denomination c ≤ a. That is O(amount × k) time and O(amount) space. The classic mistake is writing greedy for an "arbitrary denominations" problem like LeetCode 322, whose test cases include exactly the [1, 3, 4] kind of counterexample. Conversely, if the problem states that the system is canonical, or the denominations are multiples of one another ([1, 2, 4, 8]), greedy is both correct and the fastest thing you can write.

03The algorithm

1. 1Sort the denominations from largest to smallest.
2. 2For each denomination c: count = amount // c, take count coins, then amount %= c.
3. 3When the loop ends amount should be 0; anything else means this set of denominations cannot make that amount (which never happens when a 1 coin exists).
4. 4To check whether a set of denominations can be handled greedily: for every amount from 1 up to the sum of the two largest denominations, compare the greedy coin count against the DP one. If they match everywhere, the system is canonical.
5. 5If it is not canonical, switch to DP: dp[0] = 0, dp[a] = min(dp[a − c] + 1), and read off dp[amount].

04Interactive demo

Switch between the two sets of denominations and the four amounts. Greedy takes one denomination per step, and the optimum computed by DP is shown on the right. Look at what [1, 3, 4] does for 6 and for 10, and at why 27 happens to come out right again: the counterexamples do not appear at every amount, so passing a handful of test cases is no evidence that an algorithm is correct.

05Code

The greedy version, the DP version, and a function that checks whether a set of denominations is canonical. Together the three make the point of this lesson: be greedy when you can, use DP when you cannot, and know in advance which case you are in.

# Greedy change-making: largest denomination first, take as many as possible of each
def coin_change_greedy(coins, amount):
    coins = sorted(coins, reverse=True)
    result = []
    for c in coins:
        count, amount = divmod(amount, c)      # how many of this coin fit, and what is left
        result += [c] * count
    return result if amount == 0 else None    # a non-zero remainder means it cannot be made


# DP change-making (LeetCode 322): correct for any denominations, O(amount × number of coins)
def coin_change_dp(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount                 # dp[a] = fewest coins that make a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1


# Is a set of denominations "canonical" (is greedy always correct)?
# Kozen and Zaks proved that if greedy ever fails, the smallest counterexample is below the sum of the two largest coins
def is_canonical(coins):
    coins = sorted(coins)
    limit = coins[-1] + coins[-2]
    for amount in range(1, limit):
        g = coin_change_greedy(coins, amount)
        if g is None or len(g) != coin_change_dp(coins, amount):
            return False
    return True


if __name__ == "__main__":
    print(coin_change_greedy([1, 5, 10, 50], 63))   # [50, 10, 1, 1, 1]
    print(coin_change_greedy([1, 3, 4], 6))          # [4, 1, 1], but the optimum is [3, 3]
    print(coin_change_dp([1, 3, 4], 6))              # 2
    print(is_canonical([1, 5, 10, 50]), is_canonical([1, 3, 4]))   # True False

06Practice

• LeetCode 860Lemonade Change (hand back the largest notes first)Easy
• LeetCode 1710Maximum Units on a Truck (sort by value per unit)Easy
• LeetCode 322Coin Change (arbitrary denominations, so DP is required)Medium
• LeetCode 518Coin Change II (counting the ways, also DP)Medium
• LeetCode 279Perfect Squares (another case where greedy is wrong)Medium