Find Two Missing Numbers

Moderate

0/80

Average time to solve is 25m

10 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

Sample Output 1 :

2 4
2 3

Explanation of Sample Input 1 :

The two elements that are missing in the range [1, 6] are 2 and 4.
The two elements missing in the range [1,3] are 2 and 3.

Sample Input 2 :

Sample Output 2 :

2 5
1 7

Hint 1

Hint 2

Does keeping track of numbers help?

Approaches (2)

Approach 1

Approach 2

Keep Track of Numbers

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.

Time Complexity

O(N), where N is the size of the given array.

We have to traverse the array completely. Therefore, the net time complexity will be O(N).

Space Complexity

O(N), where N is the size of the given array.

Since we are using extra space to keep track of the elements that are present.

(100% EXP penalty)

Find Two Missing Numbers

Console