Home > Algorithms, Computer Programming, Computer Science > Coin Denomination Problem !

Coin Denomination Problem !

I was asked to solve the coin denomination problem in an Interview. The problem statement is: Given an amount of money, and some coins that are used in some country ( which will definitely include at-least 1 coin of worth 1), you have to find the minimum number of coins which will be used to convert the amount of money in coins. I came up with 3 solutions ( greedy algorithm which is trivial ), recursive which is tough but costly and finally a Dynamic Programming solution. I coded the algorithm in C# which is pasted below, this code will print the minimum number of coins that will be used, but the not exactly those coins which are being used in the solution, for that very purpose we have to store some addictional information, but doing that is not that much of a tough task, so enjoy the C# code

//***************** this is portion of code

int money = 9; // set any amount of money here

int [] maxcoins = new int [money + 1];

int [] coins = { 1 , 4 , 5}; // set any values here

for( int i=0; i < maxcoins.Length; i++)
    maxcoins[i] = 10000; //this value should infact be very large

maxcoins[0] = 0;

for(int i = 1; i <= money; i++)
{
    for( int j=0 ; j < coins.Length; j++)
    {
         if( i >= coins[i])
           if( (maxcoins[i – coins[j]] + 1) < maxcoins[i])
             maxcoins[i] =  maxcoins[ i – coins[j]] + 1;
    }
}

Console.WriteLine( maxcoins[money + 1]);

I will explain the logic later. 😉

Haroon 

Advertisements
  1. Mikai
    September 12, 2006 at 1:13 am

    Hi Haroon,

    I am facing the same difficult problem for a problem set. I have tried many times to formulate my own code but I can’t seem to get the correct result.

    Can you please, either: explain to me the logic, or: send me a copy of your code.

    I will appreciate it very much, as this is an urgent problem.

    Thanks in advance.

  2. September 19, 2006 at 4:47 am

    Google preved rodnoy!
    apcservicder

  3. Sotos
    October 2, 2006 at 7:04 am

    I would like to know the logic or the code…i have the same problem but i have to find the number of minimum coins for a euro…the coins are 50, 20, 10, 5, 2, and 1 cent…..a euro has 100 cents….Can you help me please?

  4. November 24, 2006 at 6:05 pm

    Let’s say the denominations are 1, 2, 5, 8, 10. You need to find 24. Your algorithm will produce {10, 10, 2, 2} but the optimal solution is {8, 8, 8}. Any thoughts on this?

  5. Indhu Bharathi
    January 3, 2007 at 12:44 pm

    I think this problem has to be solved using 2Diamensional Dynamic Programming. http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution

  6. February 27, 2008 at 5:40 pm

    The solution that you gave is exactly the greedy algorithm, so I went ahead and wrote up what it should look like using dynamic programming in python.. 🙂

    http://cmonkeyfreeware.blogspot.com/2008/02/coin-denomination-problem.html

  7. Cmoney: Why greedy?
    May 25, 2008 at 10:34 pm

    Cmonkey, why do you say this is greedy?

    I didn’t trace either yours or Haroon’s. But both your algorithms look the same to me (structurally) if we replace your ‘CheckLeast’ with a for-loop. Both look DP to me too.

  8. Owen
    September 11, 2008 at 1:58 am

    I think this problem is quite simple.

    Let v be the value of currency I am interested in.

    Let C be the set of all coins I have.

    Let V (c), for c \in C, return the value of coin c.

    Then, define function f, taking a decimal, to be the minimum number of coins required to encode a particular value.

    f (v) = 1 + min_{c \in C} f (v – V (c))

    With base cases,

    f (0) = 0
    f (-1 .. – \infty) = \infty

    For the above example with 24, this will return 3.

    f (8) = 1 + f (0) = 1
    f (16) = 1 + f (8) = 2
    f (24) = 1 + f (16) = 3

    If we are interested in the actual coins used, then we just need to have a data structure store the coins that generate the minimum in the function above.

    This is called a dynamic programming algorithm because for a given call to f (y), with value y, if we have computed this value before then we simply return the precomputed value instead of doing the recursion anew.

    Kind regards,

    Owen.

  9. vivek
    November 8, 2008 at 7:51 pm

    i think there is a small error in the code. might be some typing mistake

    “if( i >= coins[i])”

    it should be “if( i >= coins[j])”

    i think this was why andrew was getting wrong answer

  10. December 21, 2009 at 8:53 pm

    Waqi says:
    December 17th, 2009 9:30 am

    Hi Guys,
    My Name is Waqi and i collect coins. Checkout my collection. But i haven’t uploaded all of my collection yet. I got around more then 30,000 coins. So its not easy to upload all, it will take a bit time.

    http://www.omnicoin.com/?collection=WAQIAHMED

    Waqi
    waqiahmed@hotmail.com

  11. August 31, 2011 at 7:27 am

    I dont think ur solution is working

  12. August 30, 2013 at 7:17 am

    static void Main(string[] args)
    {

    double [] denom = new double[6] {100,50,10,5,1,0.50};
    double [] coins = new double[6];
    double result;
    double amt = Convert.ToDouble(Console.ReadLine());

    for (int i = 0; i < denom.Length ; i++)
    {
    result = amt / denom[i] ;
    amt = amt % denom[i];
    coins[i] = Math.Truncate(result);
    }

    for (int j = 0; j = 1)
    {
    Console.WriteLine(“${0} = {1}”,denom[j],coins[j]);
    }
    }
    Console.Read();
    }

  1. May 4, 2012 at 12:20 am

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

%d bloggers like this: