Coin systems in Python: when greedy coin change is optimal

Why this matters

A cashier who gives change needs to pay an amount with as few coins as possible. Most cashiers do this without thinking. They take the biggest coin that still fits, then the next biggest, and so on until the amount is paid. This habit is called the greedy rule, because it grabs the largest piece available at each step without looking ahead.

The greedy rule is fast and easy to write. It is also not always right. Whether it is right depends on the coin values. With the coins used in many countries it always gives the fewest coins. With some made-up coin sets it fails, and a program that trusts it will return a wrong answer with no error message.

This lesson shows how to test a coin set. You will write a Python program that runs the greedy rule, runs a slower method that always finds the true minimum, and compares the two. When they disagree, you have a counterexample: one amount where greedy uses more coins than needed.

The earlier lessons in this module cover greedy choices for intervals and jumps. The question here is different. The greedy rule is fixed, and the coin values decide whether it works.

The greedy rule in plain words

Take an amount, say 67 cents, and a list of coin values in cents: 1, 5, 10 and 25. The greedy steps are:

1. Take the largest coin that is not bigger than what is left. The largest coin is 25. Two 25s fit in 67, leaving 17.
2. The largest coin not bigger than 17 is 10. One 10 fits, leaving 7.
3. The largest coin not bigger than 7 is 5. One 5 fits, leaving 2.
4. The largest coin not bigger than 2 is 1. Two 1s fit, leaving 0.

The greedy answer is six coins: 25, 25, 10, 5, 1, 1. That is the fewest possible for 67 cents with these coins.

A coin system is the list of coin values a currency offers. A coin system is called canonical when the greedy rule always gives the fewest coins for every amount. The US coin system (1, 5, 10, 25) is canonical. The coin system 1, 3, 4 is not, as the next section shows.

A first counterexample by hand

Use the coins 1, 3 and 4 and the amount 6.

Greedy takes the largest coin that fits. The largest coin not bigger than 6 is 4. After taking one 4, 2 is left. Only 1s fit, so greedy takes two 1s. The total is three coins: 4, 1, 1.

The best answer is two coins: 3 and 3. Greedy missed it because it grabbed the 4 first, and the 4 left an awkward remainder of 2.

So the coin system 1, 3, 4 has a counterexample: the amount 6, where greedy uses 3 coins and the best is 2. One counterexample is enough to prove that greedy is not always optimal for that coin system.

Finding a counterexample by hand is easy when the coins are small. With large coins, or with many coins, a computer should do the search. That is what the rest of this lesson builds.

Two ways to count coins

The program needs two ways to count the coins for an amount.

The first is the greedy rule, as described above. It is quick: for each coin in order from largest to smallest, take as many as fit.

The second method finds the true minimum. It is called dynamic programming, which is a way of solving a big question by solving smaller questions first and saving the answers. Here the small question is "what is the fewest coins for amount a?", and the answer for amount a is built from answers for smaller amounts.

The idea works like this. Let best[a] be the fewest coins that make amount a. For amount 0, the answer is 0 coins. For any other amount a, try each coin c that is not bigger than a. If you use coin c last, the rest of the amount is a minus c, and its answer is best[a - c]. So the candidate total is best[a - c] + 1. The answer for a is the smallest candidate over all coins.

For the coins 1, 3 and 4 and the amount 6, the table fills like this:

The table has one row for each amount, and each row only looks at earlier rows. This is why the method is fast enough for amounts in the hundreds or thousands.

The Python program

The program below holds both methods and a search that compares them. Save it as coin_check.py. It uses only the standard library module math, which comes with Python, so no install is needed. Run it with python3 coin_check.py.

The output on Python 3.14 is:

[1, 5, 10, 25] -> canonical up to bound
[1, 2, 5] -> canonical up to bound
[1, 2, 4, 8] -> canonical up to bound
[1, 3, 4] -> counterexample 6
  greedy 3 coins, optimal 2
[1, 5, 6, 9] -> counterexample 11
  greedy 3 coins, optimal 2
[1, 3, 4, 5] -> counterexample 7
  greedy 3 coins, optimal 2
greedy(1,3,4 for 6) = 3
optimal(1,3,4 for 6) = 2
greedy(1,5,6,9 for 11) = 3
optimal(1,5,6,9 for 11) = 2
greedy(5,10 for 3) = -1
US mismatches up to 500: 0

Several Python pieces appear in the code. sorted(coins, reverse=True) returns a new list with the coins from largest to smallest. The // operator is floor division: it divides and drops the remainder, so 67 // 25 is 2. math.inf is Python's value for infinity, and it is larger than any number, so it works as "not reached yet". The list [0] + [math.inf] * amount joins a list with one 0 and a list of amount infinities. The last line of the __main__ block uses sum with a generator expression. A generator expression is like a list comprehension in round brackets, and it produces one value at a time, so the list of 500 results is never built in memory.

Read the output line by line. For the coins 1, 3, 4 and 1, 5, 6, 9 and 1, 3, 4, 5, the program finds a counterexample and prints the greedy count and the best count. For the coins 1, 5, 10, 25 and the other canonical sets, it finds no counterexample below its limit. The last check runs every amount from 1 to 500 for US coins and finds no mismatch.

Why the search has a finite limit

The program does not test every possible amount. It tests amounts from 1 up to the sum of the two largest coins, minus 1. For the coins 1, 3, 4 that limit is 4 + 3 - 1 = 6, and the counterexample 6 sits right at the edge.

The reason is a known result from 1994, by Dexter Kozen and Shmuel Zaks. They proved that if a coin system is not canonical, then its smallest counterexample is below the sum of its two largest coins. So if no counterexample shows up below that limit, none exists at any amount. The test is exact. It is not a guess based on a sample.

The limit depends on the coin set, so the search stays short for small coin sets. For the US coins the limit is 25 + 10 - 1 = 34, so the program checks only 34 amounts to prove the US coins canonical. The extra check up to 500 in the main block is there to show the result holds past the limit, as the theorem says it must.

The proof is not needed to use the program. It is enough to know that the search covers a finite range, and that the range is chosen so that no counterexample can hide past it.

Worked example: the coins 1, 5, 6 and 9

This coin set is less obvious. The coin 5 looks like a useful step, and the coin 6 is close to it. The program reports a counterexample at 11.

Greedy for 11 takes 9 first, since 9 is the largest coin that fits. That leaves 2, which takes two 1s. Greedy uses 9, 1, 1: three coins.

The best answer is 5 and 6. Both fit exactly and make 11 with two coins.

The lesson for the reader is this. A coin set can look sensible and still break greedy. The only way to be sure is to test it, either with a search like the one above or with a proof for a specific family of coins.

A harder example: why the search runs to the limit

Take the coins 1, 6 and 10 and the amount 12. Greedy takes 10, then two 1s: three coins. The best is 6 and 6: two coins.

This counterexample is at 12, and the limit for this coin set is 10 + 6 - 1 = 15. So the search has to go past 12 to find the smallest one. A test that only checked a few round amounts, such as 10, 20 and 50, would miss it.

Put these lines in a file that starts with from coin_check import find_counterexample, greedy_count, optimal_count. Importing the file does not run its test block, so only these lines print.

coins = [1, 6, 10]
print(find_counterexample(coins))   # prints 12
print(greedy_count(coins, 12))      # prints 3
print(optimal_count(coins, 12))     # prints 2

Coins without a 1

The program assumes the coin 1 is in the set. This matters. Without a 1, greedy can get stuck. Take the coins 5 and 10 and the amount 3. No coin fits, so greedy cannot pay the amount at all.

The program reports this as -1:

greedy(5,10 for 3) = -1

A -1 means the greedy rule did not finish, so there is no greedy count to compare with the best count. For this lesson, always include the coin 1 when you test a coin set.

Common mistakes

Forgetting to sort the coins. The greedy rule needs the coins from largest to smallest. greedy_count sorts a copy of the coins before it runs. If you write your own version and loop over the coins in the order they were typed, greedy can pick a small coin too early. Then it uses more coins than it should, and a test against the true answer shows a mismatch that comes from the bug, not from the coin system.

Sorting the list you were given. sorted() returns a new list and leaves the original alone. The method list.sort() sorts the list in place, which changes the list the caller still holds. This small example shows the difference:

coins = [1, 25, 5]
print(sorted(coins, reverse=True))
print(coins)
coins.sort(reverse=True)
print(coins)

The output is:

[25, 5, 1]
[1, 25, 5]
[25, 5, 1]

The first line is the new sorted list. The second line shows that coins did not change. The third line shows the change made by coins.sort. Use sorted() when you want to keep the original order.

Using large amounts. optimal_count creates a list with one slot per amount. For an amount of one billion, that list would be very large. The check below measures the size of a list on this machine. It creates a list of 1000 zeros and a list of 2000 zeros:

import sys
 
print(sys.getsizeof([0] * 1000))
print(sys.getsizeof([0] * 2000))

The output here was:

8056
16056

The difference is 8000 bytes for 1000 extra slots, so each slot costs 8 bytes on this machine. One billion slots would need about 8 gigabytes for the list alone. The numbers can be different on other machines. The method is meant for amounts in the thousands or less.

Stopping the search too early. A test that checks only the first 10 amounts can miss a counterexample. The limit in find_counterexample is there for this reason.

Passing a single coin. The limit uses the two largest coins. With only one coin, there is no second coin. ordered[-2] looks for the second item from the end, and a list with one item has no such item. Python stops with this error:

IndexError: list index out of range

The traceback above that line shows the file and line number where the error happened. The fix is to return early when there are fewer than two coins:

if len(ordered) < 2:
    return -1

A single coin, with the value 1, is always canonical, since every amount is just that coin repeated.

Practice

Try each exercise on paper first. Then run the program to check your answer.

1. Is the coin set 1, 4, 5 canonical? If not, give the smallest counterexample and the greedy and optimal counts for it.

Show the answer

No. The limit is 5 + 4 - 1 = 8, so check amounts 1 to 8. Amounts 1 to 7 all match. At 8, greedy takes 5, then three 1s, which is 4 coins. The best is 4 and 4, which is 2 coins. The smallest counterexample is 8, with greedy using 4 coins and the optimal using 2.

2. The coin set 1, 6, 10 has a counterexample at 12. Explain in your own words why greedy takes three coins for 12, and name the two coins the best answer uses.

Show the answer

Greedy takes the largest coin that fits first. The largest coin not bigger than 12 is 10. After taking 10, 2 is left, which needs two 1s. That is 10, 1, 1: three coins. The best answer uses two 6s, which make 12 exactly.

3. Without changing the code, predict the output of greedy_count([5, 10], 15). Then explain why the result differs from greedy_count([5, 10], 3).

Show the answer

The output is 2. Greedy takes 10, then 5, and both fit exactly. Amount 3 gives -1, because no coin fits and the amount is not a multiple of 5 or 10. The difference is that 15 can be paid with the two coins, while 3 cannot be paid at all with these coins.

4. A coin set has the values 1, 2, 5, 10, 20, 50, 100 and 200. The program prints "canonical up to bound". Explain what this message means, and why it is accurate for this coin set.

Show the answer

It means no counterexample exists below the limit, which is 200 + 100 - 1 = 299. By the result from Kozen and Zaks, a counterexample would have to be below that limit, so none exists for any amount. The message is accurate, and this coin set is canonical. The program prints the words "up to bound" to make clear that the search checked the limit, not every amount.

5. Predict which of these coin sets are canonical: [1, 2, 3], [1, 3, 4], [1, 5, 8] and [1, 2, 4, 5]. Then pass each one to report and compare.

Show the answer

Only [1, 2, 3] is canonical. The other three each have a counterexample. For [1, 3, 4] it is 6. For [1, 5, 8] it is 10, where greedy takes 8, 1, 1 (three coins) but 5 and 5 make 10 with two coins. For [1, 2, 4, 5] it is 8, where greedy takes 5, 2, 1 (three coins) but 4 and 4 make 8 with two coins. The program prints canonical up to bound for [1, 2, 3] and a counterexample for the other three.

Summary

• The greedy rule takes the largest coin that fits, again and again. It is fast, but it is not always the fewest coins.
• A coin system is canonical when greedy gives the fewest coins for every amount. The US coins are canonical. The coins 1, 3, 4 are not.
• A counterexample is one amount where greedy uses more coins than the best answer. Dynamic programming gives the true best answer for each amount.
• The search only needs to test amounts up to the sum of the two largest coins, minus 1. This limit comes from a known result, so the test is exact.
• The coin 1 must be in the set, or greedy can get stuck. sorted() gives you a sorted copy of the coins without changing the original list.