nums has n + 1 entries, and every entry is an integer from 1 to n. So at least one value must occur twice. You're told that exactly one value occurs more than once (it may occur many times); every other value occurs at most once.
Write find_repeated(nums) that returns that value.
- Don't modify
nums(no sorting, no marking entries). - Use only O(1) extra memory: no set, dict, counting array or copy of the list. The tests measure your peak memory.
1 <= n <= 300,000. Aim for O(n) time.
find_repeated([2, 4, 1, 3, 4]) # 4
find_repeated([2, 5, 1, 1, 4, 3]) # 1
find_repeated([1, 1]) # 1
find_repeated([4, 4, 2, 4, 4]) # 4
Show hint
Read each entry as an arrow from position i to position nums[i]. Start at position 0 (which nothing points to) and keep following arrows: you must end up going round a loop, and the position where you first enter it is special.