### ErenZ's blog

By ErenZ, history, 5 months ago,

I was trying this question

and for some reason that i dont understand my code doesn't work that is following.

int rec(int n, vector<int>&v){
if(n == 0){
return 1;
}

if(v[n] != -1){
return v[n];
}
return v[n] = rec(floor(n/2),v) + rec(floor(n/3),v);
}

void solve() {
vector<int>v(n+1,-1);
cout<<rec(n,v)<<endl;

}



but the following code which has the same logic works.

map<ll, ll> mp;
ll calc(ll x) {
if (x == 0)return 1;
if (mp.find(x) != mp.end())return mp[x];
ll res = calc(x / 2) + calc(x / 3);
return mp[x] = res;
}
void solve() {
ll n; cin >> n;
cout << calc(n) << "\n";
}

• 0

 » 5 months ago, # |   0 Auto comment: topic has been updated by ErenZ (previous revision, new revision, compare).
 » 5 months ago, # |   +8 floor(x/2) and x/2 do not always give the same output see this
 » 5 months ago, # |   +4 Highest value of n is 1e18.A vector with this size will exceed memory limit. If you use map it will only store required states.In every step n will reduce to either n/2 or n/3 so there will be states of order log2(n) and log3(n) which will be within memory limit
 » 5 months ago, # |   0 As stated in the problem statement, the maximum possible value of $n$ here is $10^{18}$. The constructor for a vector immediately allocates memory for its storage. Here, the vector will try to allocate space to store $f(x)$ for all $x$ from $0$ to $n$, even if the vast majority of these spaces are not actually used. Therefore, by creating a vector with size $n+1$ with the line vectorv(n+1,-1);, a 'memory limit exceeded' verdict or a runtime error may be caused.On the other hand, a map only allocates storage for a particular index when it is used. Since not every value of $f(x)$ for $x$ from $0$ to $n$ is used, the map only stores the results relevant to computing the final result, which takes much less memory and will work for this problem.Hope the above explanation helps!