Let me count the ways

After making a purchase at a large department store, Mel’s change was 17 cents. He received 1 dime, 1 nickel and 2 pennies. Later that day, he was shopping at a convenience store. Again his change was 17 cents. This time he received 2 nickels and 7 pennies. He began to wonder, “How many stores can I shop in and receive 17 cents change in a different configuration of coins? After a suitable mental struggle, he decided the answer was 6. He then challenged you to consider the general problem.

Write a program which will determine the number of different combinations of US coins (penny: 1c, nickel: 5c, dime: 10c, quarter: 25c, half-dollar: 50c) which may be used to produce a given amount of money.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CountWays
{
    class Program
    {
        static void Main(string[] args)
        {
            //US coins (penny: 1c, nickel: 5c, dime: 10c, quarter: 25c, half-dollar: 50c)
            Console.Write("Enter number of cents: ");
            string inputString = Console.ReadLine();
            int inputCents = int.Parse(inputString);
            int numberOfWays = 0;
            for (int h = 0; h <= inputCents/50; h++) //half-dollar
            {
                for (int q = 0; q <= inputCents/25; q++) //quarter
                {
                    for (int d = 0; d <= inputCents/10; d++) //dime
                    {
                        for (int n = 0; n <= inputCents/5; n++) //nickel
                        {
                            for (int p = 0; p <= inputCents; p++) //penny
                            {
                                if (p + (5 * n) + (10 * d) + (25 * q) + (50 * h) == inputCents)
                                {
                                    numberOfWays++;
                                }
                            }
                        }
                    }
                }
            }
            Console.WriteLine("There are " + numberOfWays + " ways to produce " + inputCents + " cents change");
        }
    }
}

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s