### Making Perfect Change with the Fewest Coins

Tue, Feb 10, 2009 2-minute read

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.

``````\$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