• 1 ≤ amount ≤ 10⁴
• 1 ≤ denominations.length ≤ 12
• Every denomination is a positive integer, and the supply of each is unlimited
• The denominations are assumed canonical, so the greedy choice is always optimal

A greedy algorithm builds an answer by repeatedly making the choice that looks best right now, never reconsidering. It never looks ahead and never backtracks. When that works, it is wonderful — usually one sort and one pass. The catch, which this problem exists to teach, is that the locally best choice is not always part of a globally best answer, and greedy has no way to notice when it has gone wrong.

So the real skill in every greedy problem is not writing the loop — that part is trivial. It is proving that the greedy choice is safe. This page is where we learn to distrust greedy until we have that proof, using the friendliest possible example: making change.

To make an amount with the fewest coins, the obvious move is: take the largest coin that still fits, subtract it, repeat. With everyday coins 1, 5, 10, 25 and amount 30, you take a 25, then a 5 — two coins, and clearly nothing beats two here.

def coin_change_greedy(coins, amount):
    coins.sort(reverse=True)         # largest first
    count = 0
    for coin in coins:
        if amount == 0:
            break
        take = amount // coin        # as many of this coin as fit
        count += take
        amount -= take * coin
    return count if amount == 0 else -1

Sort is O(D log D) for D denominations, the pass is O(D), and there is no dependence on the amount at all — vastly faster than building a table.

It is tempting to accept "take the biggest" as obvious, but it is not obvious — it is a property of these particular denominations, and it needs an argument. Here is the shape of that argument for the 1-5-10-25 system.

Suppose the optimal solution for some amount used fewer than the greedy number of the largest coin that fits. Then it must make up the difference with smaller coins — and for a canonical system you can always show that some bundle of those smaller coins can be swapped for one larger coin without increasing the count. For instance, any optimal solution that uses five or more 1s could replace five of them with a single 5, contradicting the claim that it was optimal. Push that reasoning through every denomination and you get: the optimal solution must use exactly as many of each large coin as greedy does. That "swap small coins for a bigger one without making things worse" move is called an exchange argument, and it is the standard way to prove any greedy algorithm correct. Keep the name — it returns on every greedy page.

Now the whole point. Change the denominations to [1, 3, 4] and ask for 6.

Greedy walked confidently off a cliff, and — this is the dangerous part — it produced a perfectly reasonable-looking wrong answer, with no error and no warning. The exchange argument above breaks for [1, 3, 4]: after taking the 4, the remaining 2 cannot be built from a single bigger coin, so the swap that made greedy safe for canonical systems is unavailable.

Six coins, and because this system is canonical the exchange argument guarantees no plan does better.

Now the cautionary run, amount = 6, coins = [1, 3, 4]: greedy returns 3, but the true minimum is 2. Same code, wrong answer — because the precondition (canonical system) does not hold.

This problem is really a lesson about greedy in general, disguised as arithmetic. The reusable habits:

Every remaining greedy problem in this section — activity selection, jump game, gas station, fractional knapsack, the interval problems — is an exercise in finding the safe greedy choice and arguing why it is safe. The arithmetic changes; the discipline does not.