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

2 Responses 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

  2. Kent writes:

    There should be 2 nickles and 1 dime ( for a sum of 99 cents), instead of 1 nickel and 2 dimes (for a sum of 104 cents).

Leave a Reply