1. Идея

Нужно посчитать, сколько разных чисел встречается в массиве.

Удобный способ — сначала отсортировать все коды. После сортировки одинаковые значения окажутся рядом. Тогда останется пройти по массиву слева направо и посчитать, сколько раз значение меняется.

2. Наблюдения

• Если массив отсортирован, то все одинаковые элементы идут подряд.
• Значит, каждое новое значение можно обнаружить сравнением с предыдущим элементом.
• Первый элемент всегда образует первый различный вид, поэтому ответ можно начать с 1.
• Дальше для каждого i от 1 до n - 1:
  • если a[i] != a[i - 1], значит встретился новый вид, увеличиваем счётчик.

Пример:

-1 0 -1 1 0 1

После сортировки:

-1 -1 0 0 1 1

Теперь смотрим на переходы:

• -1 → -1 — ничего нового
• -1 → 0 — новый вид
• 0 → 0 — ничего нового
• 0 → 1 — новый вид
• 1 → 1 — ничего нового

Всего 3 различных значения.

3. Алгоритм

1. Считать n.
2. Считать массив из n чисел.
3. Отсортировать массив.
4. Завести переменную distinct = 1.
5. Пройти по массиву с индекса 1 до n - 1.
6. Если текущий элемент не равен предыдущему, увеличить distinct.
7. Вывести distinct.

4. Почему это работает

После сортировки все одинаковые элементы стоят подряд. Это означает, что каждое различное значение образует ровно одну непрерывную группу.

Тогда число различных значений равно числу таких групп:

• первая группа начинается с первого элемента;
• каждая следующая группа начинается в позиции i, где a[i] != a[i - 1].

Алгоритм как раз считает:

• 1 за первую группу;
• плюс по 1 за каждый переход к новому значению.

Значит, итоговый счётчик точно равен количеству различных элементов в массиве.

5. Сложность

• Сортировка массива: O(n log n)
• Один проход по массиву: O(n)

Итоговая сложность: O(n log n)

Дополнительная память:

• если не считать память под сам массив, то существенных дополнительных структур не используется;
• в целом храним только массив из n элементов.

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

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

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

    int distinct = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] != a[i - 1]) {
            distinct++;
        }
    }

    cout << distinct << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

a.sort()

distinct = 1
for i in range(1, n):
    if a[i] != a[i - 1]:
        distinct += 1

print(distinct)