CSES Problem Set Solution (Distinct Number)

 Solution In C++

Distinct Numbers problem is from the category of Sorting and Searching . Its the first problem of this section. The problem statement can be read here.

This is a very basic problem which requires us to count the number of distinct integer values. Time limit is one second and constrain for every i'th integer value is 10^9. So for the array where we are going to store the integers we'll take the type as long long int. We will take a counter to count distinct values. Which cannot be greater than n (number of integer values). We can solve the problem in following approach:

We will sort the array first then iterate through the array having a variable temp (which will temporarily store the current value which we will use while iterating if its the same value or not. If not, temp will be updated and count will increment. As we sorted the array same values will appear once in a substring.  this can be visualized below:

This problem can also be solved using a set. A set is a data structure that stores unique elements . So if we use a set after inserting all the inputs we print the size it will give us a right answer. Code for both of the method is given below.

Method 1:

#include<bits/stdc++.h>

using namespace std;

int main()

{

int n;

cin>>n;

vector<long long int> a(n);

for(int i=0;i<n;++i)

cin>>a[i];

sort(a.begin(),a.begin()+n);

/*for(int i=0;i<n;++i)

cout<<a[i]<<" ";*/

long long int temp=a[0],count=1;

for(int i=0;i<n;++i)

{

if(a[i]==temp)

continue;

else if(a[i]!=temp)

{

temp=a[i];

count++;

}

}

cout<<count;

}

Method 2:

#include<bits/stdc++.h>

using namespace std;

int main()

{

int n;

cin>>n;

set<long long int> a;

for(int i=0;i<n;++i)

{

long long int k;

cin>>k;

a.insert(k);

}

cout<<a.size();

}