Coins in Change under $1

Date: 03/13/2001 at 12:45:51
From: LP FLOYD
Subject: Coins

It's been a long time since my last math class. Is there a formula or 
equation for determining the smallest number of coins a person could 
receive when given change less than $1.00?  

Ex:  Item costs $.68. Customer gives cashier $1.00 and receives $.32 
in change. What is the smallest number of coins the customer could 
receive for his change?  

I know this is easy to figure out by looking at it, but I'd like a 
standard formula or equation, if there is one, to use in a more 
complex problem.

Date: 03/13/2001 at 16:32:47
From: Doctor Rob
Subject: Re: Coins

Thanks for writing to Ask Dr. Math.

There is a cumbersome formula, and a rather easy algorithm. Here [[x]] 
means to round x down to the nearest whole number.

Suppose for simplicity that half-dollars are excluded. Then the number 
of coins that make up N cents is given by

  [[N/25]] +
     [[(N - 25*[[N/25]])/10]] +
     [[N/5]] - 5*[[N/25]] - 2*[[(N - 25*[[N/25]])/10]] +
     N - 5*[[N/5]].

The first line is the number of quarters, the second the number of
dimes, the third the number of nickels, and the fourth line the
number of pennies. This can be simplified a little to

   N - 4*[[N/5]] - [[(N - 25*[[N/25]])/10]] - 4*[[N/25]].

If you allow fifty-cent pieces, the formula is

   N - 4*[[N/5]] - [[(N - 25*[[N/25]])/10]] - 4*[[N/25]] - [[N/50]].

If you also allow dollar coins, throw in another term on the end of
-[[N/100]].

The algorithm is to give as many of the largest coins as possible,
then the next largest coin, and so on.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/