top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Find total number of ways to make change using given set of coins

+2 votes
357 views

Given an infinite supply of coins of denominations {20,10,5,1}, find out total number of way to make change of given amount - 'n'?
For example, if given amount is 20, there are 10 ways to make this change as shown below -
(1 of 20),(1 of 10 + 2 of 5),(1 of 10 + 1 of 5 + 5 of 1),(1 of 10 + 10 of 1), (2 of 10), (1 of 5 + 15 of 1),(2 of 5 + 10 of 1),(3 of 5 + 5 of 1),(4 of 5),(20 of 1)

If the amount given is 0 then the total number of ways to make change is 1 - using 0 coins of every given denomination.

posted Jul 31, 2016 by Hasan Raza

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

Algorithm:
1. consider 20, 10, 5, 1 and take amount as N=20
2. if 20%20==0 then cnt=1
3. if 20%10==0 then cnt=2
4. 20%5==0 => cnt=3 and 20%1==0 => cnt=4
5.20%10!=0 , 20%5!=0, 20%1!=0 so no increment in cnt
6.10%20!=0, 10%5==0 =>cnt=5, 10%1!=0 and similarly for other elements
7. therefore cnt ll be 10 at last.

#include <stdio.h>

int main()
{    
    int a[]={20,10,5,1};
    int n=4;
    int N=20;
    int cnt=0;
    int i,j;

    for(i=0;i<n;i++)
    {
        if(  (N%a[i]) ==0)
            cnt++;
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
            if( (a[i]%a[j])==0)
            {
                cnt++;
                if(i==j) //20%20==0, 10%10==0, 5%5==0, 1%1==0 those ll be included in the above line **cnt++**, so i am decrementing cnt
                    cnt--;
            }
    }

    printf("%d",cnt);
}
answer Aug 24, 2016 by Sneha Maganahalli
Similar Questions
+1 vote

Given an array of denominations and array Count , find minimum number of coins required to form sum S.

for example:

  coins[]={1,2,3};
  count[]={1,1,3};

i.e we have 1 coin of Rs 1 , 1 coin of Rs 2 , 3 coins of Rs 3.

Now if we input S = 6 then output should be 2 with possible combination : 3+3 = 6

+5 votes

Input: {5, 8, 5, 3, 3, 2, 7}
Output: {5, 8, 3, 2, 7, ?, ?}

Idea is that we should remove the duplicate number from the array and should return the array in the original form (obviously without duplicate).

Please help me with an efficient algorithm or C code.

...