Find Two Missing Numbers

Posted: 1 Mar, 2021
Difficulty: Moderate


Try Problem

You are given an array of unique integers where each element in the array is in the range [1, N]. The array has all distinct elements, and the array’s size is (N - 2). Hence, two numbers from the range are missing from this array. Your task is to return the two missing numbers.

For Example :

If ‘N’ = 6
[1, 3, 6, 5]
Then the output will be 2 4.

Input Format :

The first line of input contains an integer T denoting the number of test cases.

The first line of each test case contains 1 integer N, where ‘N’ - 2 is the number of elements of the array.

The second line of each test case contains ‘N’ - 2 space-separated integers, denoting the array elements.

Output Format :

For each test case, print the two numbers from the range that are missing from this array.

The output of each test case will be printed in a separate line.

Note :

Print the result in increasing order.

Constraints :

1 <= T <= 5
1 < N <= 5000
1 <= ARR[i] <= N

Where 'ARR[i]' is the i'th element of the given array.

Time Limit: 1 sec

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.
Approach 1

The idea is to keep track of all the numbers and find which ones are missing from the array, therefore :

  • Take a boolean array visited that keeps track of all the elements present in the array.
  • Iterate from 1 to n, check for every element if it is marked as true in the boolean array.
  • If the element is marked false, then that is our answer, and add it to the answer array.
  • Return the answer array.
Try Problem