There are set of coins of {50, 25, 10, 5, 1} paise in a box. Write a program to find the number of ways a 1 rupee can be created by grouping the paise.

#include <stdio.h>

int onerupee()
{

int sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;

int count = 0;

for(sum1 = 0 ; sum1 < 100; sum1 += 50) //for 50 paise
{
for(sum2 = sum1; sum2 < 100; sum2 += 25) //for 25 paise
{
for(sum3 = sum2; sum3 < 100; sum3 += 10) //for 10 paise
{
for(sum4 = sum3; sum4 <= 100; sum4 += 5) //for 5 paise
{
count++; //remaining 1 paise
}
}
if(sum3 == 100) // Here sum can become > 100
count++;
}
count++;
}
count++;

return count;
}


int main()
{
printf("Count = %d\n", onerupee());
}
Advertisements

6 thoughts on “There are set of coins of {50, 25, 10, 5, 1} paise in a box. Write a program to find the number of ways a 1 rupee can be created by grouping the paise.

  1. Hi, How about this code.Very simple but standard DP question. Although you can optimize the below code by storing the already calculated value in a table.#include int n;int make_change (int a[], int curr_cap, int i) { if (curr_cap > 100) return 0; if (i >= n) return 0; if (curr_cap == 100) return 1; return make_change(a, curr_cap+a[i], i) + make_change (a, curr_cap, i+1);}int main () { scanf ("%d", &n); int i, a[n]; for (i=0; i<n; i++) scanf ("%d", &a[i]); printf ("%d\n", make_change (a, 0, 0)); return 0;}

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