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

100 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

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);
}
``````
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

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