Given a set of coin denominations — an unlimited supply of each — and a target amount, find the fewest coins that sum to it exactly. This is the classic change-making problem. The greedy idea is the one a cashier already uses without thinking about it: take as many of the current-largest denomination as fit without going over what's left, then move to the next-smaller denomination, and repeat until the amount hits zero — no lookahead, no reconsidering an earlier choice. This is the site's fourth entry filed under Greedy, after Huffman Coding, Activity Selection, and Fractional Knapsack — and the first one where whether the rule is even correct depends on the specific denominations handed to it, not just on the shape of the problem.
On familiar currency — {1, 5, 10, 25}, U.S. pennies/nickels/dimes/quarters — greedy
is provably optimal for every amount (see Why it works). Change the denominations even slightly and
that guarantee disappears entirely: a set of denominations where greedy is always optimal is called
canonical; one where it isn't, isn't. Whether a given set is canonical isn't obvious
from looking at it — see Pitfalls for two denomination sets, each differing from U.S. currency by a
single coin, where greedy gets the wrong answer, one of them so badly it finds no answer at all.
Enter comma-separated denominations and a target amount, press Load, then Step or Run. Each step takes as many of the current-largest remaining denomination as fit, or skips it if none do. The bar fills left to right as coins are taken; each chip below it tracks how many of that denomination have been used so far. The demo also computes the true minimum via dynamic programming for comparison (capped at amount 5000 so that stays instant) — so a greedy answer that falls short, or fails outright, is visible immediately, not just claimed.
amount filled
Whether this greedy rule is even correct depends entirely on which denominations are on the table
— a genuinely different situation from every other greedy entry on this site, where the rule's
correctness is a property of the problem, not of the specific input data. For the U.S. coin
system {1, 5, 10, 25} used as this page's default, though, it's provably optimal, and
the proof is a sequence of local exchanges rather than one global argument.
Take any optimal way to make some amount N out of pennies, nickels, dimes, and
quarters, and look for an improving swap:
None of these swaps can ever make a solution worse, so any optimal solution that doesn't already
satisfy all three bounds isn't actually optimal — a contradiction. That pins pennies to at most 4,
nickels to at most 1, and dimes to at most 2, which together cover at most
4 + 5 + 20 = 29 cents without a single quarter — so any amount needing more than that
forces at least one quarter too, and the same kind of swap argument (trade coins worth 25¢ for
one quarter whenever that's possible without breaking the bounds above) forces the quarter count as
high as it can go without overshooting N. Pin all four counts down this way and there's
only one combination left standing — and it's exactly the one greedy computes, largest denomination
first. Finishing the last step in full generality (why the forced quarter count is exactly
floor(N/25) for every possible remainder, not one less) is routine casework this page
won't spell out line by line; instead, it's checked directly — greedy's coin count matches a
from-scratch dynamic-programming optimum for every amount from 0 to 20,000, not just asserted to.
None of the three swap arguments above are specific to the abstract numbers 1, 5, 10, 25 — they work because each larger denomination happens to be reachable, cheaply, from a small combination of smaller ones in this specific system (5 pennies, 2 nickels, 3 dimes-worth). Change the denominations and that stops being true — see Pitfalls.
function greedyChange(denominations, amount) {
const sorted = [...denominations].sort((a, b) => b - a);
let remaining = amount;
const used = [];
for (const c of sorted) {
const count = Math.floor(remaining / c);
if (count > 0) {
used.push({ value: c, count });
remaining -= count * c;
}
}
return { used, remaining }; // remaining > 0 means greedy couldn't finish
}Non-canonical denominations: greedy finds a solution, just not the best one.
Coins {1, 15, 25}, amount 30: sorted largest first, greedy takes one
25 (5 left), 15 doesn't fit into 5, so it falls
back to five 1s — 6 coins total. The true optimum, confirmed by the demo's
own dynamic-programming check, is two 15s: 2 coins. A quarter is the single
most valuable coin at or below 30, so greedy commits to it immediately — a commitment
that burns exactly the 5 a second 15-coin would have needed instead, and
greedy never reconsiders a choice once made.
Non-canonical denominations: greedy can fail completely, even when a solution
exists. Coins {3, 5}, amount 11: sorted largest first, greedy
takes two 5s (10), leaving 1 — and no coin in
{3, 5} is ≤ 1, so it gets stuck with a nonzero remainder and no
solution. But 3 + 3 + 5 = 11 is a real, valid solution (3 coins) that
greedy never finds, because committing to two 5s forecloses it. This is a strictly
worse failure than the previous one: not just non-minimal, but wrong in the strongest sense —
reporting "impossible" when it isn't. Contrast with coins {5, 10}, amount
4: greedy also gets stuck there, but that amount genuinely can't be made from those
denominations at all (the demo's own DP check agrees: no solution exists). "Greedy got stuck" alone
doesn't say which of these happened, so the demo always cross-checks against its DP result before
choosing which of the two messages to show, rather than treating every stuck state as the same kind
of failure.
Whether greedy fails isn't a property you can check with one example amount. The
same coins {1, 3, 4}: amount 6 fails (greedy takes
4 + 1 + 1 = 3 coins, the optimum is 3 + 3 = 2), but amount 8
with the identical denominations succeeds (greedy takes 4 + 4 = 2 coins, matching the
optimum exactly). Trying one amount and generalizing to "this coin system is fine" or "this coin
system is broken" either way is exactly the mistake this pair guards against — whether a set of
denominations is canonical is a property of the whole system across every amount, not something a
single successful or failed example settles. Determining canonicity in general is itself a real,
solved-but-nontrivial algorithmic question that this page doesn't implement; the demo's live DP
comparison is the practical stand-in — for the exact input in front of you, it always tells you
whether greedy matched, instance by instance, rather than claiming to know in advance.
Time: O(d log d), where d is the number of distinct
denominations — entirely the cost of the initial sort. The pass after that is O(d), one
floor-division per denomination, independent of the amount's size: there's no per-unit loop, which is
why the demo doesn't slow down at amount 5000 versus amount 40.
Space: O(d) for the sorted list and the used breakdown. This demo's own
dynamic-programming optimal-count comparison, shown purely for contrast, is O(amount ×
d) and capped at amount 5000 for exactly that reason — the same caveat pattern as
Activity Selection's brute-force cap,
nothing the greedy algorithm itself needs.
See Choosing a Greedy Strategy for how this entry compares against the site's other nine Greedy entries — short version: this is the category's one Tier 2 entry, exact only for canonical denomination sets, with no way to tell canonicity from the numbers alone.