CSES problem set : Distinct Numbers

CodeChef-DSA-learners dsa-learning-session
, ,
1

Here’s the question link :
https://cses.fi/problemset/task/1621

Here’s my solution using unordered maps ( I know that sets can be used here but I want to know what’s wrong with my solution, it’s giving TLE in few testcases where n=1e5 and answer should be also 1e5 ) :
https://cses.fi/problemset/result/2310768/

2

I am not able to see the solution.

3

Code is not visible with that link

4

Your solution is not visible. There’s no need to use set or map just sort array and check for a[i]!=a[i-1].
Here’s sample code:

    vi v;input(v,n);
    sort(v.begin(),v.end());
    ll ans = 0,prev = -1;
    for(auto i:v){
        if(i!=prev){
            prev = i;
            ans++;
        }
    }
    cout<<ans;
1 Like
5

i use quicksort for this
#include <bits/stdc++.h>
using namespace std;
int mang[100000000];

void bublesort(long long a,long long b)// sắp xếp bublesort từ nhỏ đến lớn
{
for(int i=a;i<b;++i)
{
for(int j=i+1;j<=b;++j)
{
if(mang[i]>mang[j]) swap(mang[i],mang[j]);
}
}
}
void quicksort(long long a,long long b)//sắp xếp quick từ nhỏ đến lớn
{
long long i=a,j=b;
long long mid=mang[(i+j)/2];
while(i<=j)
{
while(mang[i]<mid) i++;
while(mang[j]>mid) j–;
if(i<=j)
{
swap(mang[i],mang[j]);
i++;
j–;
}
}
if(a<j) quicksort(a,j);
if(i<b) quicksort(i,b);

}

int main () {
int n ;
cin >> n;
for (int i=1;i<=n;i++) {
cin >> mang[i] ;
}
quicksort(1,n) ;
int ans = 1;
for (int i=1;i<n;i++) {
ans += (mang[i]!=mang[i+1]);
}
cout << ans << endl ;
return 0 ;
}