Loading...
Loading...
Loading...
A list holds n + 1 ticket numbers, each between 1 and n. One number appears more than once, and every other number appears at most once. Find the repeated number without changing the list and with O(1) extra space.
Example 1
Input
3 1 3 4 2
Output
3
Example 2
Input
1 3 4 2 2
Output
2
Two items hold the value 2.
Try the problem first. Open one hint at a time.
Treat each value as the index of the next item. A repeated value means two items lead to the same place, so the chain loops.
Find the loop with a slow and a fast pointer, then restart one pointer from the start to find where the loop begins.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor