1. Идея

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

Если таких чисел несколько, выбирается наименьшее из них.

Главная идея проста:

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

Для подсчёта удобно использовать словарь или хеш-таблицу:

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

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

Наблюдение 1. Нужно знать частоту каждого значения

Последовательность может содержать до 2 * 10^5 чисел, а сами числа могут быть очень большими по модулю, поэтому нельзя завести массив частот по значению.

Зато можно хранить только те значения, которые реально встретились. Для этого подходит словарь:

• ключ — значение a_i;
• значение — сколько раз оно встретилось.

Наблюдение 2. После подсчёта остаётся выбрать лучший ответ

Пусть для некоторого числа value его частота равна freq.

Тогда это число лучше текущего ответа, если выполняется одно из условий:

• это первый рассмотренный элемент;
• freq > bestFreq;
• freq == bestFreq, но value < bestValue.

То есть сначала максимизируем частоту, а при равенстве минимизируем само значение.

Наблюдение 3. Порядок обхода словаря не важен

Словарь или unordered_map не обязаны хранить элементы в отсортированном порядке. Но это не мешает решению, потому что мы явно сравниваем кандидатов по правилу задачи.

3. Алгоритм

1. Считать n.
2. Считать n чисел.
3. Создать словарь частот.
4. Для каждого числа увеличить его счётчик на 1.
5. Завести переменные для ответа:
   • bestValue — лучшее число;
   • bestFreq — его частота.
6. Пройти по всем парам (значение, частота) в словаре.
7. Если текущая пара лучше ответа по правилу задачи, обновить ответ.
8. Вывести bestValue и bestFreq.

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

Докажем, что алгоритм действительно находит правильный ответ.

После первого прохода по массиву в словаре cnt для каждого числа x хранится ровно количество его появлений в последовательности. Это верно, потому что каждый раз, когда встречается x, мы увеличиваем cnt[x] на 1.

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

• его частота максимальна;
• если есть несколько чисел с такой частотой, выбирается наименьшее.

Во втором проходе мы рассматриваем каждое число value с его частотой freq и сравниваем с текущим лучшим ответом.

Обновление происходит, если:

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

Значит, после обработки всех элементов словаря в bestValue будет храниться именно то число, которое:

• имеет максимальную частоту;
• среди всех таких чисел минимально.

А bestFreq будет равна числу его вхождений.

Следовательно, алгоритм корректен.

5. Сложность

Пусть n — длина последовательности.

• Подсчёт частот: в среднем O(n).
• Поиск лучшего элемента среди записей словаря: O(k), где k — число различных значений, k <= n.

Итоговая средняя сложность: O(n).

Память:

• хранится словарь частот для всех различных чисел;
• это 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 bestValue = 0;
    int bestFreq = -1;
    bool first = true;

    for (auto it = cnt.begin(); it != cnt.end(); ++it) {
        long long value = it->first;
        int freq = it->second;

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

    cout << bestValue << " " << bestFreq << "\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

best_value = None
best_freq = -1

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

print(best_value, best_freq)