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.

Expected approach

• Math route: S = sum shortfall = a + b; Q = square-sum shortfall = a² + b²; solve the pair (a+b, a·b from (S² − Q)/2 → quadratic). Overflow-safe alternative — XOR: x = XOR of all values and 1..n = a XOR b; split all numbers by any set bit of x into two groups; XOR each group → a and b separately. O(n)/O(1) both; the XOR partition trick is the stronger answer. Marking/in-place tricks if mutation is allowed.