# Making Perfect Change with the Fewest Coins

I’ve long wondered exactly how few coins you need in your pocket in order to perfectly round out any bill. I usually grab a handful and hope it works out. Even that mathematically astute technique sometimes leaves me a nickel or few pennies short, though, so I settle for making change that gets me a quarter back instead of yet another handful of ore.

Even this settle-for-second-best option isn’t that great. It can cause permanent damage to unsuspecting cashiers that aren’t so good at math. Wondering why you would ever give them \$1.13 for a \$0.88 bill, they’ll often just give you your change back AND then the stack of coins they were originally planning to load you up with.

Well, no longer.

It turns out that you need exactly 10 coins in your pocket: 3 quarters, 2 dimes, 1 nickel, and 4 pennies. With these in your arsenal, you can make perfect change for any bill.

How can you be sure? Brute force is your friend, as is PowerShell, of course.

 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 \$coins = @{ 0.25 = 0; 0.10 = 0; 0.05 = 0; 0.01 = 0 } function SelectCoins([Decimal] \$change) {     \$result = \$coins.Clone()     foreach(\$denomination in \$coins.Keys | Sort -Desc)     {         while(\$change -ge \$denomination)         {             \$change -= \$denomination             \$result[\$denomination]++         }     }         \$result } \$results = 1..99 | % { SelectCoins (\$_ / 100) } foreach(\$denomination in \$coins.Keys | Sort -Desc) {     (“{0:c}: “ -f \$denomination) +         (\$results | % { \$_[\$denomination] } |              Measure-Object -Max).Maximum }

Gives:

\$0.25: 3
\$0.10: 2
\$0.05: 1
\$0.01: 4

### One Response to “Making Perfect Change with the Fewest Coins”

1. Stefan Decuypere writes:

Euro-peans need only 8:
EUR0.50: 1
EUR0.20: 2
EUR0.10: 1
EUR0.05: 1
EUR0.02: 2
EUR0.01: 1
(and I have not used the 1 and 2 EURO coins.)
Thanks for the script.
Stefan