Find two missing numbers in 1..n

Problem An array holds the numbers 1..n with exactly two missing. Find both missing numbers.

Input / Output

• Input: int array of length n−2 with distinct values from [1, n].
• Output: the two missing values.

Constraints

• O(n) time, O(1) space expected; watch overflow in the sum-of-squares route.

Example

• n = 5, arr = [1,4,3] → missing 2 and 5.