Back to DSA sheet
Find Duplicate Number
MediumArraysAn array of n+1 integers holds values in the range [1, n], so by the pigeonhole principle at least one value repeats. Exactly one value is duplicated (possibly many times). Find it without modifying the array and using O(1) extra space.
Input format (stdin): the first line has the array length m. The second line has m integers. Output the duplicated value.
Examples
Input: 5
1 3 4 2 2
Output: 2
2 appears twice.
Input: 5
3 1 3 4 2
Output: 3
3 appears twice.
Constraints
- 2 <= m <= 10^5
- values in [1, m-1]
- exactly one value repeats
Sheets
Blind 75NeetCode 150Striver A2Z
find-duplicate-number.cpp3 sample tests
Loading editor
Test results
Run the sample tests to check your solution against expected output.
Custom input (stdin)
Output
Run your code to see its output.