Find the Duplicate Number

Problem An array of n+1 integers has every value in [1, n], so at least one value repeats. Exactly one value is duplicated (possibly multiple times). Find it WITHOUT modifying the array and using O(1) extra space.

Input / Output

• Input: int array nums (length n+1). Output: the duplicated value.

Constraints

• No mutation, O(1) space — rules out sorting, hash sets, and mark-by-negation; O(n) time achievable.

Example

• [1,3,4,2,2] → 2; [3,1,3,4,2] → 3.

Expected approach

• Floyd's cycle detection on the implicit linked list i → nums[i]: the duplicate is the cycle's entry. Phase 1: slow/fast until they meet; phase 2: restart one pointer at index 0, advance both singly — meeting point is the answer. O(n)/O(1). Explain the array-as-function-graph reduction — it's the entire question. Fallback under relaxed constraints: binary search on value counting ≤ mid (O(n log n), still O(1) space).