Least Coins Calculator

Being new to this country, I wasn't quite used to the usage of Quarters (25 cents). It was so bad that I was caught in a supermarket once trying to figure out how best to produce 62 cents! The cashier finally got impatient with me and told me, "Yes, yes! Give me one of that kind of coin!" It was really embarrassing. Hence below is a javascript program that will help to formulate, given a cents amount, the combination that will utilise the least coins.

(Actually the program is not important. It is the thinking process while creating this program that helps me to straight things out! Check out the proof below.)

Proof

The algorithm used is similar to that of the Greedy approach in computer algorithms. Given the cents amount (=a), first we try to use up as many quarters as possible. Let the number of quarters be q1. The remaining cents amount should now be strictly less than 25 cents. Next we try to use up as many dimes as possible. Let the number of dimes used be d1. The remaining cents amount should now be less than 10 cents. Next we try to use up as many five cents as possible. Let the number of five cents used be f1. The remaining cents amount should now be less than 5 cents. Finally the balance is met using one cents. Let the number of one cents used be n1.

(It is not obvious that the above algorithm will give the least coins combination in all cases. Imagine a currency with coins of value 1-cents, 5-cents, 25-cents, and 40-cents. Consider the case where we need to produce 50 cents amount. Using the above algorithm we shall use 1 40-cents and 2 5-cents -- a total of 3 coins. But the actual least coins combination should be 2 25-cents -- a total of 2 coins. See the below proof to show that the algorithm works in the case of quarters and dimes!)

Now suppose there is a combination of coins [q2, d2, f2, n2] that gives the least total number of coins. We shall show that [q1=q2, d1=d2, f1=f2, n1=n2].

Note 1 To give the least number of coins, 0 <= n2 <= 4. If n2 >= 5 instead, then exchanging a five cents coin for 5 one cent coins will yield a lesser combination (contradiction).

Note 2 Similary, 0 <= f2 <= 1. If f2 >= 2 then exchanging a dime for 2 five cents coins will yield a lesser combination (contradiction).

Note 3 Furthermore, 0 <= d2 <= 2. If d2 >= 3 then exchanging a quarter and a five cents coin for 3 dimes will yield a lesser combination (contradiction).

Note 4 Finally, if d2 = 2, then f2 = 0. Suppose d2 = 2 and f2 > 0, then exchanging a quarter for 2 dimes and a five cents coin will yield a lesser combination (contradiction).

Note 5: q1 >= q2; given q1 = q2, we have d1 >= d2; given q1 = q2 and d1 = d2, we have f1 >= f2
This is by construction of our algorithm.

Claim 1 : q1 = q2.
Proof If q2 < q1, then value of d2, f2, and n2 must contain a 25 cents. This is not possible with the above Notes. The above Notes imply that the maximum value of d2, f2 and n2 is 24 cents. Hence by Note 5, q2 = q1.

Claim 2 : d1 = d2.
Proof If d2 < d1, then value of f2 and n2 must contain a 10 cents. This is not possible with the above Notes. The above Notes imply that the maximum value of f2 and n2 is 9 cents. Hence by Note 5, d2 = d1.

Claim 3 : f1 = f2.
Proof If f2 < f1, then value of n2 must contain a 5 cents. This is not possible with the above Note 1. Note 1 implies that the maximum value of n2 is 4 cents. Hence by Note 5, f2 = f1.

Claim 4 : n1 = n2.
Proof By claims 1 - 3, the remaining unrepresented amount must be equal in both combinations. Hence n1 = n2.

Hence we have proved that [q1=q2, d1=d2, f1=f2, n1=n2]. Hence the algorithm noted above gives the least coins combination.