Always Have Exact Change With Only 10 Coins!
I hate having spare change. Change sucks because it usually just sits in your house and it’s a waste of money. I found a way to use the change you have and never get change back when purchasing with cash. With a set of just 10 coins, you can make change for any amount from 1 cent to 99.
I’ve already read about the 10 coins somewhere else online. It’s not really interesting to have the answer given to you. Since I’m a nerdy computer scientist, I was trying to come up with an algorithm to produce this set of coins. I came up with an iterative solution that goes like this:
Start out with no coins.
From 1 to 99 cents:
If you can make exact change for the current amount, go to the next amount.
Otherwise, try adding the largest denomination coin to your set of coins (a quarter) that will allow you to pay the exact amount. If it’s too big, go to the next smallest until you hit a penny.
End Loop.
I came up with this in the shower. When I got out and tried it, it actually worked! Here’s a portion of the trace through the loop:
No coins, I need to make change for 1 cent. Add a penny. Yay, I can make change for one cent!
…
4 pennies, need to make change for 5 cents. Add a nickel.
…
4 pennies 1 nickel, need to make change for 10 cents. Add a dime.
And so on. I believe the algorithm works because it uses a greedy heuristic of choosing the largest denomination coin first before defaulting to the penny. Am I a nerd? Yes.
Oh, I just realized I didn’t actually say which 10 coins were the ones you need. They’re 4 pennies, one nickel, two dimes, and three quarters. You can also do it with two nickels and one dime but that’s not what my algorithm came up with, plus two dimes are lighter than two nickels!
Have fun getting rid of your change!