Distinct Numbers

Distinct Numbers
CSES easy

You are given a list of \(n\) integers. Find the number of distinct values in the list.

Constraints:

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le x_i \le 10^9\)

Input:

  • First line: integer \(n\) — the number of values.
  • Second line: \(n\) integers \(x_1, x_2, \dots, x_n\).

Output:

  • One integer — the number of distinct values.

Example:

Input:

5
2 3 2 2 3

Output:

2
Solution with a set

A set stores each value only once: inserting a value that is already in the set does nothing. We insert all \(n\) values into a set, and the size of the set is the answer.

Each insertion takes \(O(\log n)\) time, so the whole solution takes \(O(n \log n)\) time.

#include <iostream>
#include <set>
using namespace std;

int main() {
    int n;
    cin >> n;

    set<int> values;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        values.insert(x);  // a repeated value is not inserted again
    }

    cout << values.size() << "\n";
}
Solution with sorting

After sorting, equal values are next to each other. So a value \(x_i\) appears for the first time exactly when \(i = 0\) or \(x_i \ne x_{i-1}\). We count these positions.

Sorting takes \(O(n \log n)\) time and the loop takes \(O(n)\) time, so the whole solution takes \(O(n \log n)\) time. This solution needs no container other than the array itself.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> x(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }

    sort(x.begin(), x.end());

    int distinct = 1;  // x[0] is always a new value
    for (int i = 1; i < n; i++) {
        if (x[i] != x[i - 1]) {
            distinct++;
        }
    }

    cout << distinct << "\n";
}