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 more than once). Find it without modifying the array and using O(1) extra space.

Input / Output

• Input: int array of length n+1, values in [1, n]. Output: the duplicated value.

Constraints

• No mutation, O(1) extra space; O(n) time achievable.

Example

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