1. Идея

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

Если смотреть на числа в отсортированном порядке, можно поддерживать переменную need — минимальный положительный номер, который мы пока ещё не встретили.

Сначала need = 1, потому что в первую очередь нас интересует число 1.

Дальше идём по массиву:

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

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

Наблюдение 1

Отрицательные числа и ноль не могут быть ответом, потому что нужен именно положительный номер.

Поэтому такие элементы можно просто игнорировать.

Наблюдение 2

Повторы тоже не создают проблем.

Например, если числа такие: 1 1 2 2 3, то второй 1 уже ничего не меняет: число 1 и так занято.

Наблюдение 3

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

Например, после сортировки массива -3 0 2 2 5 получим:

-3 0 2 2 5

Начинаем с need = 1.

• -3 < 1, пропускаем
• 0 < 1, пропускаем
• 2 > 1, значит числа 1 нет, ответ 1

Наблюдение 4

Если мы уже встретили все числа от 1 до k, то следующий кандидат на ответ — k + 1.

Именно это и хранит переменная need.

3. Алгоритм

1. Считать n и массив a.
2. Отсортировать массив.
3. Установить need = 1.
4. Пройти по всем элементам массива:
   • если a[i] < need, пропустить;
   • если a[i] == need, увеличить need на 1;
   • если a[i] > need, остановиться: ответ уже найден.
5. Вывести need.

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

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

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

Изначально это верно: до просмотра элементов не встретилось число 1, значит need = 1.

Теперь рассмотрим очередной элемент:

• Если x < need, то он не может изменить ответ.

  • Если x <= 0, он вообще не является положительным кандидатом.
  • Если x положительное, но меньше need, значит оно уже было учтено раньше или это повтор. Поэтому минимальное отсутствующее число остаётся тем же.

• Если x == need, то число need теперь найдено среди выданных номеров. Значит оно больше не может быть ответом, и нужно искать следующее минимальное отсутствующее число, то есть увеличить need на 1.

• Если x > need, то из-за сортировки все следующие элементы будут не меньше x, а значит тоже больше need. Следовательно, число need уже нигде не встретится. Значит именно оно — наименьшее отсутствующее положительное.

Таким образом, после завершения прохода need и есть правильный ответ.

5. Сложность

Основное время тратится на сортировку:

• время: O(n log n)
• память: O(1) дополнительной памяти, если не считать хранение самого массива

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());

    long long need = 1;
    for (int i = 0; i < n; i++) {
        if (a[i] < need) {
            continue;
        }
        if (a[i] == need) {
            need++;
        } else {
            break;
        }
    }

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

7. Код на Python 3

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

a.sort()

need = 1
for x in a:
    if x < need:
        continue
    if x == need:
        need += 1
    else:
        break

print(need)