How Many Ways to Make a Dollar

I ran into a reminder of an interesting programming problem the other day. One I meant to use with students but never did. Other teachers I know do use it. Simply pot, how many possible combinations of coins are there that add up to a dollar. It’s easily solved with a set of nested loops like the ones below.

int count = 0;

for (int halves = 0; halves <= 2; halves++)
{
     for (int quarter = 0; quarter <= 4; quarter++)
     {
         for (int dimes = 0; dimes <= 10; dimes++)
         {
             for (int nickels = 0; nickels <= 20; nickels++)
             {
                 for (int penny = 0; penny <= 100; penny++)
                 {
                     int value = halves * 50 + quarter * 25 + dimes * 10 + nickels * 5 + penny;
                     if (value == 100)
                     {
                         count++;
                     }
                 }
             }
         }
     }
}
Console.WriteLine(count);

It’s pretty straight forward. The key thing is understanding what coins there are and what their value it. The code above doesn’t include a dollar coin. Should it? Probably but it depends on the way the problem is specified. Also these are the coins currently being minted. Over the history of the country there have been a number of other coins in circulation

US TREASURY: What denominations of coins are no longer being produced?

There are quite a few denominations of coins that the United States Mint does not produce any longer for general circulation. They are the half-cent coin, the two-cent coin, the three-cent coin, the half-dime coin (although it was replaced by the five-cent coin), a twenty-cent coins, and the various denominations of gold coins. Although the Mint does produce a series of gold bullion coins, these are not intended for circulation.

The problem would be more interesting if some of these were allowed. I keep thinking that there must be another way to solve the problem though. I just can’t think of what it might be.

[Edit] Jeremiah Simmons shared information about solving this problem using Dynamic Programming. It's more complicated but scales better. Take a look. Understanding The Coin Change Problem With Dynamic Programming

It is so sawesome when educators share ideas with each other.