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() {
read(n);
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";
}
Auto comment: topic has been updated by ErenZ (previous revision, new revision, compare).
floor(x/2) and x/2 do not always give the same output see this
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
As stated in the problem statement, the maximum possible value of $$$n$$$ here is $$$10^{18}$$$. The constructor for a
vectorimmediately 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 avectorwith size $$$n+1$$$ with the linevector<int>v(n+1,-1);, a 'memory limit exceeded' verdict or a runtime error may be caused.On the other hand, a
maponly 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!