I'm facing a very weird problem and I don't quite understand it. The problem is of finding the number of distinct integers in an array of numbers specifically [This CSES problem](https://cses.fi/problemset/task/1621/).↵
Note that the limit of N is 2e5 Hence O(N) and O(NlogN) both solutions should pass. However the funny part is that my O(N) solution gets TLE in one of the subtasks and O(NlogN) gets AC. I'm really confused and would appreciate if someone could tell me what is going on. Thanks in advance.↵
↵
My O(NlogN) solution: Inserting elements in a set↵
int main(){↵
ll n;↵
cin>>n;↵
set <ll> s;↵
ll x;↵
for(ll i=0;i<n;i++) {cin>>x; s.insert(vec[i]);}↵
cout<<s.size()<<endl;↵
return 0;↵
}↵
↵
My O(N) solution: Insterting elements in an unordered_map↵
int main(){↵
ll n;↵
cin>>n;↵
ll cnt=0;↵
ll x;↵
unordered_map <ll,ll> umap;↵
for(ll i=0;i<n;i++) {↵
cin>>x;↵
if(!umap[x]){↵
umap[x]++;↵
cnt++;↵
}↵
}↵
cout<<cnt<<endl;↵
return 0;↵
} ↵
set <ll> s; ↵
ll x; ↵
for(ll i=0;i<n;i++) {cin>>x; s.insert(vec[i]);} ↵
cout<<s.size()<<endl; ↵
return 0; ↵
} ↵
↵
My O(N) solution: Insterting elements in an unordered_map ↵
int main(){ ↵
ll n; ↵
cin>>n; ↵
ll cnt=0; ↵
ll x; ↵
unordered_map <ll,ll> umap; ↵
for(ll i=0;i<n;i++) { ↵
cin>>x; ↵
if(!umap[x]){ ↵
umap[x]++; ↵
cnt++; ↵
} ↵
} ↵
cout<<cnt<<endl; ↵
return 0; ↵
} ↵
Note that the limit of N is 2e5 Hence O(N) and O(NlogN) both solutions should pass. However the funny part is that my O(N) solution gets TLE in one of the subtasks and O(NlogN) gets AC. I'm really confused and would appreciate if someone could tell me what is going on. Thanks in advance.↵
↵
My O(NlogN) solution: Inserting elements in a set↵
int main(){↵
ll n;↵
cin>>n;
set <ll> s;↵
ll x;↵
for(ll i=0;i<n;i++) {cin>>x; s.insert(vec[i]);}↵
cout<<s.size()<<endl;↵
return 0;↵
}↵
↵
My O(N) solution: Insterting elements in an unordered_map↵
int main(){↵
ll n;↵
cin>>n;↵
ll cnt=0;↵
ll x;↵
unordered_map <ll,ll> umap;↵
for(ll i=0;i<n;i++) {↵
cin>>x;↵
if(!umap[x]){↵
umap[x]++;↵
cnt++;↵
}↵
}↵
cout<<cnt<<endl;↵
return 0;↵
}
set <ll> s; ↵
ll x; ↵
for(ll i=0;i<n;i++) {cin>>x; s.insert(vec[i]);} ↵
cout<<s.size()<<endl; ↵
return 0; ↵
} ↵
↵
My O(N) solution: Insterting elements in an unordered_map ↵
int main(){ ↵
ll n; ↵
cin>>n; ↵
ll cnt=0; ↵
ll x; ↵
unordered_map <ll,ll> umap; ↵
for(ll i=0;i<n;i++) { ↵
cin>>x; ↵
if(!umap[x]){ ↵
umap[x]++; ↵
cnt++; ↵
} ↵
} ↵
cout<<cnt<<endl; ↵
return 0; ↵
} ↵
