14,022,565 members
See more:
I was trying to solve the question on basic recursion using memoization https://www.spoj.com/problems/COINS/

NOTE-> max value of n is 1 000 000 0000

I definitely must add memoization to solve this problem
But when i am declaring array of size `1 000 000 000` compiler is saying std::bad_alloc
If I don't declare this much size than very large nearly equal to 100000000(greater then array size) then I am getting segmentation fault

well some people recommended me to use map ,in map also we have to insert all the
key and assign the value -1
otherwise when recursion will start like for some very large how we can a map return value which is not stored as a key till now

Can someone help how map is going to work here to optimize space complexity in this case ?

What I have tried:

```#include<bits/stdc++.h>
using namespace std;
vector <int> dp(100000,-1);
int exchange(int n){
if(n<12)
return n;
if(dp[n]!=-1)
return dp[n];
return dp[n] = exchange(n/2)+exchange(n/3)+exchange(n/4);
}
int main(){
//   int t;
// cin>>t;
while(1){
//      memset(dp,-1,sizeof(dp));
int n;
cin>>n;
cout<<exchange(n)<<endl;
}

}
```
Posted
Updated 7-Jan-19 22:32pm

## Solution 1

Quote:
But when i am declaring array of size `1 000 000 000` compiler is saying std::bad_alloc

Your problem is that you did not analyze the problem, you are jumping strait to the second most simple minded solution which replaced the brute force solution by another brute force solution, in another way.
Think about it, if n= 1 000 000 000, the largest smaller value you will ever used is 500 000 000. Not a single value between those 2 values will ever be used to solve the problem.
Simply cascading the n/2 reduction will give you 30 values in worst case.
You have to find a way to avoid declaring the 1 000 000 000 values in an array or anything.
v2
kavinderrana121 8-Jan-19 4:51am

How did you calculate total unique sub problem in this case
Patrice T 8-Jan-19 5:07am

1 000 000 000 is < 2^30, so repeatedly dividing by 2 should not exeed 30 times.

Top Experts
Last 24hrsThis month
 OriginalGriff 151 CPallini 128 Dave Kreskowiak 100 Richard MacCutchan 70 Christian Graus 64
 OriginalGriff 2,288 Dave Kreskowiak 815 Patrice T 814 Richard Deeming 718 MadMyche 696