В списке содержатся 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. Следуйте условию и ограничениям выше.