В ходе просмотра видеокурса по алгоритмам и структурам данных столкнулся с задачей, которая никак не уложится у меня в голове.
Постановка задачи: Дан массив из n+1 элементов, в котором записаны числа от 1 до n. Отсюда ясно, что в этом массиве будет повторы. Необходимо найти это самое повторяющееся число. Повторяться оно может произвольное число раз.
Ограничения:
1) Время работы алгоритма: O(n);
2) Расход памяти: O(1);
3) Массив не изменяемый(immutable).
Я могу придумать решения за O(n^2), решение с использованием дополнительной памяти за O(n), решение с изменяемым массивом за то же самое O(n). Больше идей нет.
Собственно вопрос к вам, уважаемые специалисты - а вы знаете решение этой задачи? Или же вы уверенны, что она не решается и способны привести доказательство этого факта? Само решение меня на данный момент не интересует, важно лишь подтверждение факта решаемости данной задачи. Ну или же было бы интересно какое либо простое замечание, которое далеко от полного алгоритма решения, но могло бы на него натолкнуть.
Ссылка на оригинал: Лекция №5. Время, с которого идет описание задачи: 00:09:10.
