Distinct Numbers Solution

11 September 2021

Statement

( The original statement can be found here )
You are given a list of n integers, and your task is to calculate the number of distinct values in the list.

Input
The first input line has an integer n: the number of values.

The second line has n integers x1,x2,…,xn.

Output
Print one integers: the number of distinct values.

Constraints
1 ≤ n ≤ \(2\times10^5\)
1 ≤ \(x_i\) ≤ \(10^9\)
Time limit : 1.00s
Memory limit : 512MB


Example

Input :
5
2 3 2 2 3

Output :
2

Solution

We are asked to count the number of distinct elements in an array. There are several ways to approach this problem, such as using hash maps or other data structures, but I am going to explain a different idea.

The first step is to sort the array. To do this, I use the C++ sort function, which uses the \(introsort\) algorithm, which has a time complexity of \(O(n \times log(n))\).

After sorting, all the equal elements are consecutive and a simple solution arises. We iterate through the sorted sequence and check the values at indices \(i\) and \(i-1\) . If they are different, we increment the answer by \(1\) because we have found a new element.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, answer = 0;
    cin >> n;
    vector<int> values(n);
    for (int i = 0; i < n; i++) {
        cin >> values[i];
    }
    sort(values.begin(), values.end());
    for (int i = 1; i < n; i++) {
        if (values[i] != values[i - 1]) {
            answer++;
        }
    }
    cout << answer + 1 << endl;
}

The number of operations to execute this algorithm is approximately \(n \times log(n) + n\), hence the time complexity is \(O(n \times log(n))\). Since we store \(N\) elements and the \(introsort\) algorithm does not require much space, the space complexity is \(O(n)\).