## What Is the Optimal Change to Keep in Your Pocket?

I like to live fairly minimalistic. This ideology extends to my wallet, which I prefer to keep as slim as possible. For my cards I use a simplified version of the Crabby Wallet, and for my coins I have a simple coin pouch purse. Of course, the coin purse swells up rather quickly with the number of coins that are placed inside. So is there an optimal number and type of coins, that allows you to pay any reasonable amount with exact change?

This is an extended version of the change-making problem. Determining the optimal change (*i.e.* using as few coins as possible) can become a very complicated problem. Things get a lot easier for so-called canonical coin systems where a greedy algorithm always gives the best solution. This algorithm works very easily, and quickly: always pick the largest denomination of coin that is not greater than the remaining amount. Luckily for us, it’s possible to verify that the UK coin system (as well as the US and Euro coin system) is indeed a canonical coin system. What does this all mean? Well, it allows us to determine the optimal number and types of coin to have with you at all time in a greedy (and hence *quick*) way.

The remainder of this post focusses on the UK and Euro coin system (they use the same denominations). What we have in these coin systems are coins valued 0.01, 0.02, 0.05, 0.10, 0.20, 0.50, 1.00, and 2.00. The smallest note we have is 5.00. What is then the ideal number and type of coins to have with you so that:

- you don’t have to carry any more coins than needed;
- you can pay any amount less than £5/€5 in exact change?

**Let’s find out!**

We can start with payments from 0.01 – 0.10. For 0.10 we can just use the 0.10 coin. The same holds for 0.01, 0.02, and 0.05. Remember that the greedy algorithm always picks the largest denomination, so we will at least need these 4 coins on us. If we have to pay an amount of 0.03 we can use a coin of 0.02 and 0.01 (which we already have). We do have a bit of a choice to pay an amount of 0.04. We can do this by paying 0.02 + 0.01 + 0.01, or we can pay by using 0.02 + 0.02. Now, notice that we need one *extra* coin here in both cases: we either need an extra 0.01 coin or an extra 0.02 coin. Since the 0.01 coin is smaller, let’s pick that one. We can now pay any amount between 0.01 – 0.10, as we already have a 0.05 coin and we can pay any amount from 0.00 – 0.04 exactly. We have done even better than that: we can pay *any* value between 0.01 – 0.19 exactly. Indeed, for any value between 0.10 and 0.20 we simply use the 0.10 coin, and then pay the 0.01 – 0.09 difference as explained before.

Once we hit 0.20, we need an extra 0.20 coin. Since we already have all the coins to pay from 0.01 – 0.19, this means adding one extra 0.20 coin allows us to pay anything between 0.01 and 0.39. That’s not quite enough to reach the next denomination of 0.50, so we need to add an extra coin still. This can be a 0.10 coin or a 0.20 coin, but since the 0.10 is smaller it’s best to take that one. We can now pay anything between 0.00 – 0.50.

Now the proces keeps on repeating. To pay any amount between 0.50 – 1.00 we need an extra 0.50 coin, leaving an amount to be paid between 0.01 – 0.49. To pay anything between 1.00 – 2.00 we need to add an additional 1.00 coin. And then we stumble like we did before with the 0.10 – 0.20 coins. To make it all the way to 5.00 we either need to add two 1.00 coins, or two 2.00 coins. Since the first are the smallest coins, lets add two 1.00 coins and one 2.00 coin.

**That’s it!** The *smallest number of coins* you need to carry with you to pay any amount less than 5.00 with *exact change* is **11 coins**. Their denominations is as follows:

- two 0.01 coins;
- one 0.02 coin;
- one 0.05 coin;
- two 0.10 coins;
- one 0.20 coin;
- one 0.50 coin;
- two 1.00 coins;
- one 2.00 coin.

If you have these coins with you at all times, the cashier will love you and you will never have to carry any coins you won’t need anyhow.