Find the single duplicated value in an array of integers under strict constraints, without modifying the array.
Problem
You are given an array nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
Because there are n + 1 numbers but only n possible values, at least one value must appear more than once. In fact, exactly one value is duplicated, but it may appear more than twice.
Return the duplicated number.
You should solve the problem without modifying the input array and using only constant extra space.
Intuition
The repeated value creates structure that can be exploited either by treating the array like a linked list or by using a value-range binary search.
Input Format
- The first line contains an integer
nimplied by the array size. - The array
numshas lengthn + 1. - Each
nums[i]satisfies1 <= nums[i] <= n. - Exactly one value is duplicated, though it may appear multiple times.
Output Format
Return a single integer: the duplicated number.
Constraints
1 <= n <= $10^{5}$nums.length = n + 11 <= nums[i] <= n- Exactly one integer value appears at least twice
- Do not modify the array
- Use
O(1)extra space
Example 1
Input
nums = [1,3,4,2,2]
Output
2
Explanation
The value 2 appears twice, while every other value appears once.
Example 2
Input
nums = [3,1,3,4,2]
Output
3
Explanation
The duplicated number is 3.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.