### ErenZ's blog

By ErenZ, history, 4 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

By ErenZ, history, 4 months ago,

I was trying to the this question and during that, I used the following code.

void solve() {

map<int,int>mp;
for(int i = 0; i< n; i++){
int a; cin>>a;
if(mp.find(a) != mp.end()){
int b = mp[a]+1;
cout<<b<<" "<<i+1<<endl;
return;
}
else{
mp[x-a] = i;
}
}
cout<<"IMPOSSIBLE"<<endl;

}


this did not give any tle error but when i used the following code

void solve() {

unordered_map<int,int>mp;
for(int i = 0; i< n; i++){
int a; cin>>a;
if(mp.find(a) != mp.end()){
int b = mp[a]+1;
cout<<b<<" "<<i+1<<endl;
return;
}
else{
mp[x-a] = i;
}
}
cout<<"IMPOSSIBLE"<<endl;

}


it was giving tle in the test cases 23 and 24. now I know that both of them are the same except for the use of data structure, but the map should be slower than unordered_map but the opposite is true, why is this happening can anyone explain?

code of unordered_map

code for map

• 0