← All coding problems
Find the Duplicate Number
mediumArrays & Hashing+20 XPTime limit 2s
The array has n + 1 integers, each between 1 and n. So at least one value repeats — and in this problem exactly one value repeats (possibly more than twice). Find it.
Input:
- line 1:
n - line 2:
n + 1integers
Output: the repeated value.
Constraints: 1 ≤ n ≤ 10⁵.
Challenge: a set solves it in O(n) memory. The classic interview version asks for O(1) extra memory without modifying the array: treat i → a[i] as a linked list and use Floyd's cycle detection (tortoise and hare).
Sample input 1
4 1 3 4 2 2
Sample output 1
2
Sample input 2
4 3 1 3 4 2
Sample output 2
3
📖 Stuck? Learn the pattern
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).