Array/vector of size 10^9 problem

general
, , ,
1

**

question–>http://www.spoj.com/problems/COINS/
My program is working for value of n upto 10^7.Earlier i used an array
instead of vector and it was working for n upto 10^8 .I read somewhere that stack cannot
allocate 10^9*4 which is approximately 4gb of memory(which the memory required in my solution as
long int will take 4 bytes.So i went for using vectors.But now also my program
crashes for n above 10^7.What can i do so that my solution works for n upto 10^9.Plz help

**

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
long int max1(long int,vector<long int>&);
int main()
{
long long int n;
int t=10;
vector<long int> sum;
while(t--)
{
cin>>n;
for(long int i=0;i<n;i++)
{
sum.push_back(0);
}
cout<<max1(n,sum)<<"\n";
}
return 0;
}
long int max1(long int n,vector<long int>&sum)
{ if(n==1||n==0){return n;}
if(sum[n]!=0){return sum[n];}
sum[n]=max1(floor(n/2),sum)+max1(floor(n/3),sum)+max1(floor(n/4),sum);
if(sum[n]>n)
{return sum[n];}
else 
{
 sum[n]=n; return n;
}
}
2

The memory limits for the SPOJ judge permit array (or vector )length only upto 10^7. There is no option but to reduce memory usage.

Hint : Use an array upto 10^7 and for larger values , determine how you can use these values to optimize. Something like DP

3

i used vector only to memoize the values which are calculated earlier to reduce the time limit because earlier i got time limit exceeded on this question.But to reduce the time complexity i used vector.
@kcahdog thanks for the answer i will try to find a solution for higher values

4

You dont need to store all values upto 10^9. Just store the ones you come across in a map and reuse them.

Thats the best approach for it.

Still if you want to use dp you can store values upto 10^5 and compute for higher values.

My dp soln in C : link

Soln with Map(dictionary) in python : link

1 Like