n. В коробку положили n + 1 бирку, и все номера на них в этом диапазоне — значит, хотя бы один номер обязательно повторяется. Известно, что повторяется ровно один номер (он может встречаться два раза и больше), а остальные встречаются не больше одного раза.
Дан массив tags длины n + 1. Верните номер, который повторяется.
Дополнительное условие: не меняйте массив tags и используйте O(1) дополнительной памяти. Сортировка и множество посещённых значений не подходят.tags=[2, 4, 1, 3, 4] → 4
Номера от 1 до 4, бирок пять. Дважды встречается 4.
tags=[1, 1] → 1
Самый маленький случай: n = 1, и единица обязана повториться.
tags=[5, 2, 5, 1, 5, 5] → 5
Повторяющееся число может встречаться больше двух раз — здесь 5 встречается четырежды.
tags=[2, 4, 1, 3, 4]
4
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 80 тестов на сервере, включая скрытые.