← All coding problems
Missing and Repeating Number
mediumPlacement Coding+20 XPTime limit 2s
The array should contain each number from 1 to n exactly once. By mistake, one number appears twice and, as a result, one number is missing. Find both.
Input:
- line 1:
n - line 2:
nintegers
Output: two numbers — the repeating one, then the missing one.
Constraints: 2 ≤ n ≤ 10⁵.
Think about it: a count array works in O(n) extra space. For O(1) space, compare the array with 1..n: the difference of the sums gives rep − miss, and the difference of the sums of squares gives rep² − miss². Two equations, two unknowns.
Sample input 1
5 4 3 4 2 1
Sample output 1
4 5
Sample input 2
2 2 2
Sample output 2
2 1
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).