1. Идея

Нужно найти число, которое встречается в массиве чаще всего.

Самый удобный способ — посчитать, сколько раз встречается каждое значение. Для этого используем словарь:

• ключ — само число;
• значение — его частота.

После этого остаётся пройти по всем парам значение -> частота и выбрать лучший ответ:

• если частота больше текущей лучшей, берём это значение;
• если частота равна лучшей, берём меньшее значение.

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

1. Порядок элементов во входном массиве не важен. Важны только частоты.

2. Значения a_i могут быть большими и даже отрицательными, поэтому обычный массив частот использовать неудобно. Подходит именно словарь:

   • в C++ — unordered_map;
   • в Python — dict.

3. Так как по условию при равенстве частот нужно вывести наименьшее значение, недостаточно просто найти максимум по частоте. Нужно ещё корректно обработать ничью.

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

3. Алгоритм

1. Считать n.
2. Считать n чисел.
3. Создать словарь частот cnt.
4. Для каждого числа увеличить cnt[x] на 1.
5. Завести переменные:
   • answer — текущий лучший ответ;
   • bestFreq / best_freq — лучшая частота.
6. Пройти по всем элементам словаря:
   • если это первый рассмотренный ключ, сделать его текущим ответом;
   • если его частота больше bestFreq, обновить ответ;
   • если частота равна bestFreq, но значение меньше текущего answer, тоже обновить ответ.
7. Вывести answer.

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

После первого прохода по массиву в словаре cnt для каждого значения хранится точное количество его появлений.

Дальше мы перебираем все различные значения и поддерживаем инвариант:

• answer — лучшее значение среди уже просмотренных;
• bestFreq — его частота.

Что значит "лучшее":

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

Когда рассматриваем очередное значение:

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

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

5. Сложность

Пусть k — количество различных значений.

• Подсчёт частот: O(n) в среднем.
• Перебор словаря: O(k).
• Итого: O(n) в среднем.

По памяти:

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

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

6. Код на C++17

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

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

    unordered_map<long long, int> cnt;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        cnt[x]++;
    }

    long long answer = 0;
    int bestFreq = -1;
    bool first = true;

    for (const auto &p : cnt) {
        long long value = p.first;
        int freq = p.second;

        if (first || freq > bestFreq || (freq == bestFreq && value < answer)) {
            first = false;
            bestFreq = freq;
            answer = value;
        }
    }

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

7. Код на Python 3

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

cnt = {}
for x in a:
    cnt[x] = cnt.get(x, 0) + 1

answer = None
best_freq = -1

for value, freq in cnt.items():
    if answer is None or freq > best_freq or (freq == best_freq and value < answer):
        answer = value
        best_freq = freq

print(answer)