635. The One Value That Repeats
An array of m values is given, where every value is between 1 and m - 1. Exactly one
value appears more than once; it may appear twice or many times.
Print that value. Do NOT modify the array and do not use extra memory that grows with m.
1 3 4 2 2 -> 2
3 1 3 4 2 -> 3
2 2 2 2 2 -> 2
## Why the easy answers are ruled out
Sorting answers it and modifies the array. A counting table or a hash set answers it and uses
O(m) extra memory. Both restrictions are in the statement precisely to close those doors.
What is left is the observation that the array is already a FUNCTION.
## The array is a linked list in disguise
Every value is between 1 and m - 1, which are all valid positions in the array. So "go from
position i to position a[i]" is a well defined step, and following it repeatedly traces a
path.
Since there are finitely many positions, the path must eventually repeat, so it ends in a cycle. And the entrance to that cycle is a position reached from TWO different places, which means two positions hold the same value. That value is the repeated one.
Starting at position 0 is safe because no value equals 0, so position 0 is never re-entered and is therefore not inside the cycle.
## Floyd's two pointers
slow = a[0]; fast = a[a[0]]
while slow != fast:
slow = a[slow]
fast = a[a[fast]]
One pointer takes one step per round and the other takes two. They must meet inside the cycle, because the gap between them changes by exactly one each round and cannot skip over zero.
## Finding the entrance
Once they meet, reset one pointer to position 0 and advance BOTH one step at a time. They meet at the cycle entrance, which is the answer.
The reason is a short piece of arithmetic. If the path has t steps before the cycle and the
cycle has length c, the meeting point is t + k steps along for some k that is a multiple
of c minus t. Walking t more steps from the meeting point and t steps from the start
therefore lands both at the entrance.
Being able to say WHY the second phase works, rather than just writing it, is what this problem is for.
## Where else this appears
Problem 644 in this topic uses the same two pointers on a completely different sequence, and the classic use is detecting a loop in a linked list. Recognising "this is a function iterated from a start point" is what tells you Floyd applies.
## Cost
Time O(m). Space O(1).
Constraints - `2 ≤ m ≤ 200000` - every value is between `1` and `m - 1` - exactly one value repeats
Input
The first line contains an integer m, the length of the array.
The second line contains m integers, each between 1 and m - 1.
Output
Print one integer, the value that appears more than once.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.