mediumBinary SearchPure DSA~32 min
Locate the Duplicated Shard ID
A registry holds n+1 shard IDs, each in the range 1..n, so exactly one ID is duplicated. Find the duplicate without modifying the registry and using only constant extra space.
Problem
Given an array nums of n + 1 integers where each integer is in the range [1, n] inclusive, there is exactly one repeated number. Return that repeated number. You must not modify the array and must use only O(1) extra space.
Input
An integer array nums of length n+1 with values in [1, n]; exactly one value repeats (possibly multiple times).
Output
An integer: the duplicated value.
Constraints
- 1 <= n <= 10^5
- nums.length == n + 1
- 1 <= nums[i] <= n
- Only one repeated number, but it can appear more than once.
Examples
Example 1
Input
nums = [1,3,4,2,2]
Output
2
2 appears twice.
Example 2
Input
nums = [3,1,3,4,2]
Output
3
3 is the repeated value.