Find the Duplicate Number
Given an array of n + 1 integers where each integer is in the range [1, n], find the one repeated number without modifying the array and using only O(1) space.
Find the Duplicate Number

Given an array of n + 1 integers where each integer is in the range [1, n], find the one repeated number without modifying the array and using only O(1) space.

Example 1:
Input: [1,3,4,2,2]
Output: 2
Input
arr =[1,3,4,2,2]

Treat array as linked list: nums[i] points to next index. Duplicate creates a cycle.

Phase 1: Find Cycle
Phase 2: Find Entrance
Array (nums[i] = next index, like linked list)

1

[0]

3

[1]

4

[2]

2

[3]

2

[4]

Slow: 1
Fast: 1
Algorithm Insight (Floyd's Cycle Detection):

Treat array as linked list: index i points to nums[i]. The duplicate creates a cycle.
Phase 1: Slow moves 1 step, fast moves 2 steps until they meet.
Phase 2: Reset slow to start, both move 1 step - they meet at cycle entrance (duplicate).

Variables
No variables to display
DepthFunction Call
Stack empty
0/8