Click here to Skip to main content
15,746,652 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
I was trying to solve the question on basic recursion using memoization

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:

using namespace std;
vector <int> dp(100000,-1);
int exchange(int n){
        return n;
        return dp[n];
    return dp[n] = exchange(n/2)+exchange(n/3)+exchange(n/4);
int main(){
 //   int t;
   // cin>>t;
  //      memset(dp,-1,sizeof(dp));
        int n;

Updated 7-Jan-19 22:32pm

1 solution

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.
Share this answer
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.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900