Medium
Find the Duplicate Number
- Time limit
- 2 s
- Memory limit
- 256 MB
- Estimated
- 20 min
Description
Description
Given an array nums of length n + 1 where each element is an integer in the range [1, n], return the single number that appears more than once.
There is exactly one repeated number, but that number may appear more than twice. All other values appear exactly once.
You must not modify the input array.
Examples
Example 1
- Input:
nums = [1, 3, 4, 2, 2] - Output:
2
Example 2
- Input:
nums = [3, 1, 3, 4, 2] - Output:
3
Example 3
- Input:
nums = [1, 1] - Output:
1
Expected Function Behavior
Implement findDuplicate(nums) and return the repeated integer. The input array must not be modified.
Constraints
2 <= nums.length <= 1000001 <= nums[i] <= n, wheren = nums.length - 1- Exactly one value is repeated at least once; every other value appears exactly once.
- The input array must not be modified.
Sample cases
3Sample 1
Input
nums = [1,3,4,2,2]
Expected output
2
Sample 2
Input
nums = [3,1,3,4,2]
Expected output
3
Skills and languages
Patterns
- Fast and Slow Pointers
Languages
- Python 3
Solve this problem
Create a free account to write, run and submit your solution.
- Write Python or Java in the browser, with your draft saved as you type
- Run your code on the examples as often as you like
- Submit to a sandboxed judge and see exactly which case failed
- Ask the AI mentor for a hint without being handed the answer