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.