### Money Matters Solution: A recursive approach

**Problem Statement:**

**T**

**he Government of Byteland has decide to issue new currency notes with special protection features to commemorate a great mathematician.**

It has decided to issue notes summing up to N such that all the sums from 1 to N should be possible to be made by selecting some of the notes. Also this has to be done in way such that if any note from 1 to N can be made in more than one way by combining other selected notes then that set of notes is not valid.

For example, with N = 7,

The valid sets are:

{1,1,1,1,1,1,1}

{1,1,1,4}

{1,2,2,2}

{1,2,4}

Invalid sets are:

{1,1,1,2,2} beacuse the sum adds up to 7 but 2 can be made by {1,1} and {2}, 3 can be made by {1,1,1} and {1,2}, 4 can be made by {1,1,2} and {2,2} and similarly 5, 6 and 7 can also be made in multiple ways using the same set.

{1,1,3,6} beacuse all from 1 to 7 can be uniquely made but the sum is not 7 (its 11).

Before implementing this idea of issuing these new set of notes, the Government wants to know how many possible valid sets are there for a given N. Your program should help the Government to find this out.

It has decided to issue notes summing up to N such that all the sums from 1 to N should be possible to be made by selecting some of the notes. Also this has to be done in way such that if any note from 1 to N can be made in more than one way by combining other selected notes then that set of notes is not valid.

For example, with N = 7,

The valid sets are:

{1,1,1,1,1,1,1}

{1,1,1,4}

{1,2,2,2}

{1,2,4}

Invalid sets are:

{1,1,1,2,2} beacuse the sum adds up to 7 but 2 can be made by {1,1} and {2}, 3 can be made by {1,1,1} and {1,2}, 4 can be made by {1,1,2} and {2,2} and similarly 5, 6 and 7 can also be made in multiple ways using the same set.

{1,1,3,6} beacuse all from 1 to 7 can be uniquely made but the sum is not 7 (its 11).

Before implementing this idea of issuing these new set of notes, the Government wants to know how many possible valid sets are there for a given N. Your program should help the Government to find this out.

### Input

**First line will contain the number of test cases T (1<=T<=6666).**

Each test case will have one line containing an integer N (<= 2^31-1).

Each test case will have one line containing an integer N (<= 2^31-1).

### Output

**For each value of N output the total number of valid sets on a separate line.**

### Example

**Input:
3
7
111212121
1000
Output:
4
75
13**

**
**

Solution:

**//Solved by Sanjay Verma
**

#include<stdio.h>#define memSize 3333int noofsol(int);int count[memSize];main(){int t,x;count[0]=0;count[1]=1;count[2]=1;count[3]=2;count[4]=1;scanf("%d",&t);while(t--){scanf("%d",&x);printf("%d\n",noofsol(x));}return 0;}int noofsol(int x){int sum=1,i,j;if((x<memSize-1) && (count[x]!=0 || x==0))return count[x];for(i=1;i<=x;i++){for(j=1;j<=x/i;j++){if(j*i + i-1 == x)sum+=noofsol(i-1);}}if(x<memSize-1)count[x]=sum;return sum;}The original problem on codechef can be found here.Note: This is a recursive solution. For achieving faster speed, you may convert it into iterative code.If you want any clarification, please comment.~~If you like this post please subscribe to this blog by email. You can also follow it.~~

could you please explain you approach ....

ReplyDelete