It’s good to know how to make change. I am talking about the kind of change related to coins. I think for the most part, when people are taught how to make change, it’s assumed they are playing the part of the cashier. Playing the part of the wallet holder is much more common, so I want to talk about that. And I realize that soon maybe no one will be talking about change, but, hey, I had fun doing this, and improved my transaction time and wallet efficiency. Maybe you can too. Anyway, let’s make sure we’re all on the same page about the cashier role. A transaction goes like this: the wallet holder presents some goods with an associated cost and some coins to the cashier. The cashier finds the value of the coins, subtracts the cost, and returns the least number of coins that makes up that amount. By the way, when I say coins I mean bills as well. Finding the value of the coins and subtracting the cost is taught in grade school, whereas returning the least number of coins that makes up that amount is now most commonly taught on the job or in algorithms classes. In fact, the way to do it is a greedy algorithm: given the amount, give the largest denomination possible, subtract it’s value from the amount, and repeat until the amount is 0.
Right, now let’s talk about the wallet holder. The wallet holder does not have an effectively infinite number of each coin like the cashier does. The wallet holder, like the cashier, wants to reduce the number of coins involved in the transaction, but also wants to reduce the number of coins in the wallet. That’s not to say money is bad. What I mean is that a ten dollar bill is far preferred over 1000 pennies. So the wallet holder is interested in a strategy that does those things. I haven’t found any simple way to get from here to an answer. I have, however, created a Python script to help me. In it, I’ve used denominations up to 20$ and transactions with costs randomly chosen between 0$ and 40$. The wallet holder is fed twenties whenever it is short of cash.
Strategy 1: reduce the number of coins in the wallet
When the wallet holder tries to reduce the number of coins in the wallet, everything goes pretty well except when some unlucky cashier has to receive a whole bunch of small change, every once in a while. On average, the wallet contains 7.2 coins and a transaction involves 7.41 coins.
Strategy 2: reduce the number of coins in the transaction
When the wallet holder tries to reduce the number of coins in the transaction, the wallet explodes with small change.
Strategy 3: reduce the number of coins returned
Reducing the number of coins returned turns out to be the same as doing strategies 1 and 2 at the same time. That is, there wont be an unlucky cashier, and there wont be an explosion of small change. On average, the wallet contains 8.21 coins and a transaction involves 6.82 coins. I liked this one best.
Now, I used a brute force algorithm to find which coins the wallet holder should give to achieve strategy, but in real life we can’t do that. So it’s time to approximate strategy 3. This is what I came up with first: pretend you pay with your entire wallet and figure out what the change would be. Omit from the actual payment whatever coins are present in both in the payment and the change. In some sense, only pay what’s necessary, and in another sense, just don’t pay what’s stupid. It’s similar to strategy 3 in that removing stupid coins reduces the number of coins returned. At this point I imagined (and you should now too) a person who empties their entire wallet every time they buy anything and let’s the cashier deal with it (they probably also have a cell phone). Anyway, this turns out to have very nearly the same results as reducing the number of coins returned. But it’s still not easy enough.
The next simplification goes like this: assume you’re paying with your entire wallet, then in order of greatest value coin to least value coin, see how many of those coins you can omit from the payment without causing the cashier to break a larger coin. Thankfully, our denominations are such that a bigger coin is, for the most part, an integer number of smaller coins. This means you can forget about every bigger coin except the next one up. So, if you are seeing how many fives you can remove from an amount, you only have to worry about breaking a ten. This doesn’t apply to twenties and fifties, and it doesn’t apply to dimes and quarters. As I said before, not using anything larger than twenties because I think anything above is uncommon. As for dimes and quarters, we’re going to deal with that in a second, along with a final simplification. But let’s do an example that conveniently avoids the problem just to make sure everything else is clear.
- Say you have 1 penny, 1 dime, 1 twonie, 1 ten, and 2 twenties, and are charged 31.35$.
- You add up your entire wallet and get 52.11$ and pretend you are paying that.
- You subtract 31.35$ and get 20.76$.
- 20.76$ can be reduced by 20$, so you omit a twenty from your payment, and subtract 20.00$ from 20.76$ to get 0.76$.
- 0.76$ can’t be reduced by 10$.
- You don’t have any fives.
- 0.76$ can’t be reduced by 2$.
- You don’t have any loonies or quarters.
- 0.76$ can’t be reduced by 0.10$ without breaking a cashier’s quarter into smaller denominations.
- You don’t have any nickels. But if you did, this is where the quarter-dime problem happens, because if you forget about quarters, you could reduce 0.76$ to 0.71$ without breaking a cashier’s dime.
- 0.76$ can be reduced by 0.01$ without breaking a cashier’s nickel, so you omit paying a penny. You don’t worry about subtracting 0.01$ from 0.76$ because there’s nothing smaller than a penny anyway.
- You present your entire wallet minus a twenty and a penny, which is 1 dime, 1 twonie, 1 ten, and 1 twenty. This comes to 32.10$ so your change is 0.75$ which is just 3 quarters. In all, you’ve reduced the number of coins in your wallet by 1, and 7 coins were involved in the transaction.
Dealing with quarters isn’t too bad: all you do is keep both the quarter and the dime in mind when you’re working with nickels. If you had fifties, you’d have to worry about twenties and fifties when you were working with tens. And the final simplification I want to make is to split dollars and cents into two separate computations so you never have to subtract two 4-digit numbers. I’ll explain the details of how this is accomplished in the example. Note that because you’ll only have 7 coins in your wallet on average, finding the total value of all coins in the wallet should be easy.
- Say you have 1 penny, 1 nickel, 1 dime, 1 twonie, 1 ten, and 2 twenties, and are charged 31.40$.
- You add up your entire wallet and get 52.16$.
- You subtract 31$ from 52$ and get 21$. There is one detail left over from the 4-digit subtraction that we have to take care of: because the 0.40$ in the cost is greater than the 0.16$ in the wallet, we have to reduce by one dollar, so 20$. If we had 0.40$ or more in the wallet, we’d stick with 21$.
- 20$ can be reduced by 20$, so you omit paying a twenty, and subtract 20$ from 20$ and get 0$. Oh boy! We can skip right to the cents part of the computation now.
- You subtract 0.40$ from 0.16$, modulo 1.00$. That is, you subtract 16 from 40, get 24, then subtract 24 from 100 and get 76, meaning 0.76$. If you had 0.40$ or more in your wallet, you’d be on easy street and just subtract 0.40$ from that number. Anyway, 0.76$.
- You don’t have any quarters.
- 0.76$ can’t be reduced by 0.10$ without breaking a cashier’s quarter.
- 0.76$ can’t be reduced by 0.05$ without breaking a cashier’s quarter.
- 0.76$ can be reduced by 0.01$ without breaking a cashier’s nickel, so you omit paying a penny.
- You present your entire wallet minus a twenty and a penny, which is 1 nickel, 1 dime, 1 twonie, 1 ten, and 1 twenty. This comes to 32.15$ so your change is 0.75$ which is 3 quarters. You’ve reduced the number of coins in your wallet by 2, and 8 coins were involved in the transaction.
Finally, I’d like to offer you the Python script I made to help me out in evaluating strategies. You can get it here. Perhaps you can come up with even better strategies or simpler ways to implement them.