Skills101
← 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: n integers

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).

Loading editor…

Log in to run and submit your code — it's free.