Find the Duplicate Number
Part of Practice: Gaps, Clones & Carries
You are given an array nums of n + 1 integers, each between 1 and n. By the pigeonhole principle (n + 1 values squeezed into n possible numbers) at least one value must repeat — and here exactly one value repeats, possibly many times. Return that repeated value.
The hard part is the restrictions: you may not modify the array, and you must use O(1) extra space — so no sorting in place and no hash set. Target O(n) time. The array can hold up to 10^5 entries.
Examples
- Input:
- nums = [1, 3, 4, 2, 2]
- Output:
- 2
- Input:
- nums = [3, 1, 3, 4, 2]
- Output:
- 3
- Input:
- nums = [3, 3, 3, 3, 3]
- Output:
- 3
The duplicate may appear more than twice; the answer is still the repeated value.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.