1. Идея

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

Самая прямая идея: хранить все уже встреченные значения в структуре данных, которая не допускает повторов. Тогда:

• если число встретилось впервые, оно добавится;
• если такое число уже было, ничего не изменится.

После обработки всех элементов размер этой структуры и будет ответом.

Для этого удобно использовать множество (set в Python, unordered_set в C++).

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

1. Нас интересуют только различные значения, а не количество повторений.

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

2. Порядок элементов не важен.

   Не имеет значения, в каком месте встретился код цветка. Важно только, был ли он уже раньше.

3. Множество автоматически убирает повторы.

   Если несколько раз вставить одно и то же значение, в множестве оно всё равно хранится один раз.

4. Ограничение n <= 2 * 10^5 подсказывает, что решение должно работать быстро.

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

3. Алгоритм

1. Считать число n.
2. Создать пустое множество.
3. Прочитать n чисел.
4. Каждое число добавить в множество.
5. Вывести размер множества.

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

Рассмотрим, что происходит при обработке массива.

• Для каждого элемента a_i мы пытаемся добавить его в множество.
• Если такого значения там ещё нет, оно появится.
• Если оно уже есть, множество не изменится.

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

Следовательно, количество различных значений равно размеру множества.

5. Сложность

При использовании множества:

• время: в среднем O(n), так как каждая вставка работает в среднем за O(1);
• память: O(n) в худшем случае, если все элементы различны.

Это укладывается в ограничения.

6. Код на C++17

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

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

    unordered_set<long long> s;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        s.insert(x);
    }

    cout << s.size() << '\n';
    return 0;
}

7. Код на Python 3

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