Войти Регистрация
Алгоритмы

208. Задвоенный и пропавший номер платёжки

Средняя

Платёжки клиента за день пронумерованы от 1 до n. После сбоя выгрузки в списке nums длины n один номер встречается дважды, а другого нет; порядок произвольный.

Верните [задвоенный, пропавший]. Решите без словаря и без сортировки: O(1) дополнительной памяти.

В работе: Сверка выгрузки в 1С с банком: у бухгалтера 9000 платёжек, а скрипт сверки работает на потоке и не может держать в памяти отметки для каждого номера.

Пример 1

Ввод
nums = [3, 1, 4, 4, 2, 6]
Вывод
[4, 5]

Номер 4 дважды, 5 нет.

Пример 2

Ввод
nums = [1, 1]
Вывод
[1, 2]

Ограничения

  • 2 ≤ n ≤ 10⁵
  • 1 ≤ nums[i] ≤ n
  • ровно один номер дважды и ровно один отсутствует
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def dup_and_missing(nums):
МатематикаМассивСуммыцельO(n)

Источник: наша задача на данных Альфа-Банка. Условие пересказано своими словами.