Given an array of integers nums containing n + 1 integers, each in the range [1, n] inclusive, there is exactly ONE repeated number. Find it, without modifying the array and using only O(1) extra space.
Example 1
Input: nums = [1,3,4,2,2]
Output: 2
Explanation: 2 appears twice.
Example 2
Input: nums = [3,1,3,4,2]
Output: 3
Explanation: 3 appears twice.
1 <= n <= 10^5nums.length == n + 11 <= nums[i] <= nA hash set spotting the first repeated value works in O(n) time — but costs O(n) extra space, which the problem explicitly disallows.
Since every value is in [1, n], each value can be treated as a POINTER to an index — following these pointers repeatedly traces out a path.
Because there's a duplicate, that path must eventually loop back on itself — this is structurally identical to detecting a cycle in a linked list.
public int findDuplicateHashSet(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int n : nums) {
if (!seen.add(n)) return n; // add() returns false if n was already present
}
throw new IllegalArgumentException("No duplicate found");
}Time: O(n) · Space: O(n) — violates the problem's O(1) space requirement