Все задачи
Легко Решено: 2 Процент решений: 66.7%

Пропущенное число

Найдите одно число, отсутствующее в диапазоне от 0 до n.

Чему вы научитесь

  • Вычислять ожидаемую сумму 0..n
  • Находить пропущенное значение по разности
  • Решать за один проход без сортировки

Условие

В списке содержатся n различных чисел из диапазона 0, 1, …, n, то есть ровно одно число из этого диапазона отсутствует. Найдите его. (Подсказка: сравните ожидаемую сумму с фактической.)

Реализуйте функцию missing_number(numbers).

Входные данные

numbers: n различных чисел из диапазона от 0 до n.

Выходные данные

Верните отсутствующее число.

Ограничения

0 ≤ n ≤ 100 000

Примеры

Пример 1
Ввод:
numbers = [3, 0, 1]

Ожидаемый вывод:
expected = 2
Ввод:
std::vector<long long> numbers = {3, 0, 1};

Ожидаемый вывод:
long long expected = 2;
Ввод:
long[] numbers = new long[] {3, 0, 1};

Ожидаемый вывод:
long expected = 2;

Пояснение

n = 3, диапазон 0–3; отсутствует 2.

Пример 2
Ввод:
numbers = [0]

Ожидаемый вывод:
expected = 1
Ввод:
std::vector<long long> numbers = {0};

Ожидаемый вывод:
long long expected = 1;
Ввод:
long[] numbers = new long[] {0};

Ожидаемый вывод:
long expected = 1;

Пояснение

n = 1, диапазон 0–1; отсутствует 1.

Как подступиться

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

Подсказка 1

Числа должны покрывать весь диапазон от 0 до n, кроме одного пропуска.

Подсказка 2

Сравните сумму полного диапазона с фактической суммой списка.

Подсказка 3

Учтите случай, когда пропущено 0 или n.

Ожидаемая сложность

время O(n), доп. память O(1)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

# Участник Язык Время Память Оценка ИИ Решение
1 HJhettory Jurash Python 784 ms - 4/5 Посмотреть код
2 KKKaneki Ken Python 874 ms - 3/5 Посмотреть код

Учитесь у других

Решения сообщества

Внимание, спойлер: ниже 2 полных решений Попробуйте сначала решить сами. Вы всегда можете посмотреть код других и AI-обзоры. Войдите и решите задание, чтобы присоединиться к обсуждению.