Click here to Skip to main content
14,022,565 members
Rate this:
 
Please Sign up or sign in to vote.
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

1 solution

Rate this: bad
 
good
Please Sign up or sign in to vote.

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
Comments
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)

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Cookies | Terms of Service
Web01 | 2.8.190417.4 | Last Updated 8 Jan 2019
Copyright © CodeProject, 1999-2019
All Rights Reserved.
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100