Coin Change: Greedy against Optimal

Type a set of coins and an amount. The page pays the amount twice: greedily, taking the largest coin that fits until nothing is left or no coin fits, and with the fewest coins possible, found by filling a table from 0 up to the amount. Below the table, every amount up to a range you choose, marked where greedy uses more coins than it needs.

Worked example — Coin Change: Greedy against Optimal

Greedy, largest coin first	3 coins
Fewest coins, from the table	2 coins: 2×24
Coins greedy wastes here	1
Amounts from 1 to 240 where greedy loses	42 of 240
Kozen–Zaks bound: the two largest coins added	54
Smallest amount where greedy loses	48

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Coin Change: Greedy against Optimal

The change-making problem asks for the fewest coins, from a given set of denominations with any number of each, that add up to an amount. The greedy algorithm takes the largest coin that fits and repeats. Dynamic programming solves the problem exactly by solving every smaller amount first: M(0) = 0 and M(a) = 1 + min M(a − c) over the coins c ≤ a. A coin system on which greedy is optimal for every amount is called canonical.

What each symbol means

M(a): the fewest coins that make the amount a; the number in cell a of the table
G(a): the number of coins greedy uses for a
cₘ, cₘ₋₁: the largest and second-largest coins; the first amount where greedy loses, if there is one, is smaller than their sum

Assumes: An unlimited supply of every coin and whole-number denominations, with the number of coins as the only cost. A till that has run out of florins is a different problem. The bound needs a 1 among the coins; without one, some amounts cannot be paid at all, and greedy can stall short of an amount the table can pay.

Old British money beat greedy at four shillings 🖖

Press UK before 1971. To pay 48d, four shillings, greedy reaches for the largest coin that fits: a half-crown (30d), then a shilling (12d) and a sixpence (6d), three coins. Two florins at 24d each make the same 48d in two. From there greedy loses on six amounts out of every thirty pence, 48–53d, 78–83d and so on up to 228–233d: 42 of the 240 amounts in a pound. It loses each time by exactly one coin, which is why every red bar on the strip stands the same height. The six are the amounts that leave 18 to 23 pence over one or more half-crowns, where handing one half-crown back and paying 48d with two florins saves a coin. The halfpenny does not rescue it. Type the coins in halfpence, 1, 2, 6, 12, 24, 48, 60, check up to 480, and the first failure is 96 halfpence, still 48d; greedy loses on 84 of the 480 amounts, the same 42 and the halfpenny above each of them.

Take out the half-crown and greedy never fails 🖖

Press Without the half-crown. The same coins less one, 1, 3, 6, 12 and 24 pence, and the strip goes blank: greedy loses on none of the 240 amounts. Each of these coins divides the next, and in a chain like that greedy cannot lose, because any handful of one coin worth the next coin up can be swapped for that one coin. The half-crown breaks the chain. Thirty is not a multiple of twenty-four, and two florins come to a half-crown plus 18d, which takes a shilling and a sixpence to pay; every failure on the first strip is that swap. Adding a coin is not the cure either. Type 1, 3, 6, 12, 24, 30, 60 to put back the crown, five shillings: the count falls from 42 to 24, and 48d still fails first, because a crown is no help with anything smaller than itself.

Checking a coin system is a finite job 🖖

Greedy failing at 48d says nothing yet about 4,800d. What settles a system for every amount is a theorem of Dexter Kozen and Shmuel Zaks, published in 1994: with a 1 among the coins, if greedy ever loses, the smallest amount where it loses lies strictly between c₃ + 1 and c_m + c_m−1, where c₃ is the third-smallest coin and c_m and c_m−1 are the two largest. Press US cents. The two largest are 100 and 50, nothing below 150 fails, and that finite check covers every amount there will ever be; for the euro it runs to 300. The bound cannot be pulled any tighter. Press 1, 3, 4: the window between 5 and 7 holds one amount, 6, and 6 is exactly where greedy loses. The dashed line on the strip is the bound, and with a 1 among the coins the first red bar always sits to its left.

Problem solved in full

Which third coin can join 1 and 5? 3 steps
A country has coins of 1 and 5 and wants a third, d, somewhere from 6 to 30. For which d will greedy change-giving always be optimal? The page tests one system at a time; Kozen and Zaks's rule for three coins settles all 25 at once. Press 1, 3, 4 to try the rule first on a system the page has already tested.

Open this problem in the tool
1. The rule, for coins 1 < c < d: write d = qc + r with 0 ≤ r < c. The system fails somewhere if and only if 0 < r < c − q. For 1, 3, 4, d = 4 = 1 × 3 + 1, so q = 1 and r = 1, and 0 < 1 < 2 holds. It fails, and the page finds the first failure at 6:
  
  $4 = 1 \times 3 + 1 : q = 1, r = 1, 0 < 1 < 3 - 1 = 2$
2. Now c = 5, so d = 5q + r and the test is 0 < r < 5 − q. The larger q is, the less room is left for r:
  
  $d = 5 q + r, 0 \leq r < 5 : 0 < r < 5 - q$
3. For q = 1 (d from 6 to 9), r can be 1, 2 or 3, so d = 6, 7 and 8 fail. For q = 2 (10 to 14), r = 1 or 2: 11 and 12. For q = 3 (15 to 19), only r = 1: 16. From q = 4 on, 5 − q is 1 or less and no r fits:
  
  $q = 1 : d \in {6, 7, 8} q = 2 : d \in {11, 12} q = 3 : d = 16 q \geq 4 : 5 - q \leq 1$
Answer

Six values fail, 6, 7, 8, 11, 12 and 16, and the other nineteen work, every d from 17 to 30 among them. Type 1, 5, 12 to watch one of the six: greedy pays 15 as 12 + 1 + 1 + 1, four coins, where three fives do it.

$d \in {6, 7, 8, 11, 12, 16} 15 = 12 + 1 + 1 + 1 = 5 + 5 + 5$

Learning path

Why an algorithm is correct

References (3)

The bound the page draws as a dashed line and settles every system with: if greedy is ever beaten, the smallest amount where it is beaten lies strictly between c₃ + 1 and cₘ + cₘ₋₁; the three-coin rule the worked problem uses; the {1, 3, 4} example and the US system 1, 5, 10, 25, 50, 100 as canonical: D. Kozen and S. Zaks, "Optimal bounds for the change-making problem." Theoretical Computer Science 123(2), 1994, pp. 377-388. DOI 10.1016/0304-3975(94)90134-1
The pre-decimal coins and their values in pence (threepence, sixpence, shilling of 12d, florin of two shillings, half-crown of two shillings and sixpence, crown of five shillings), and the halfpenny's end as legal tender on 31 July 1969: Wikipedia contributors, "£sd", Wikipedia, The Free Encyclopedia, accessed 3 October 2026.
Which coins made up the circulating set at the end, as the Royal Mint itself issued them in 1970: half-crown, florin, shilling, sixpence, threepence, penny and halfpenny: The Royal Mint, "1970 Pre-Decimal UK Proof Set", product description, accessed 3 October 2026.

By the 42Math team · Reviewed against published sources. Corrections welcome.