Find the Duplicate Number

Problem Given an array of n+1 integers where every value lies in [1, n], exactly one value is duplicated (possibly appearing more than twice). Find that duplicate without modifying the array and using only O(1) extra space.

Input / Output

• Input: array nums of length n+1 with values in [1, n].
• Output: the single repeated integer.

Constraints

• Array length n+1, values in [1, n] — by pigeonhole a duplicate must exist.
• Read-only: the array may not be mutated (rules out in-place index marking).
• O(1) extra space (rules out a hash set or count array).
• The duplicate may repeat 2 times or many times.

Example

• Input: [1,3,4,2,2] → Output: 2
• Tricky case: [2,2,2,2,2] → Output: 2 — a value repeated n times, which trips up solutions that assume exactly two occurrences.