Distinct Numbers Solution

11 September 2021


( 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.

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

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

Print one integers: the number of distinct values.

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


Input :
2 3 2 2 3

Output :


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]) {
    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)\).