# Find Two Missing Numbers

Posted: 1 Mar, 2021

Difficulty: Moderate

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

Approach 2

The idea is to use the property of XOR that XOR of the same elements cancels each other. Therefore, our approach goes like this :

- Find XOR of all the array elements and natural numbers from 1 to ‘N’, for example, Let N = 5 and the array be arr[] = {1, 3, 5}.

XOR = (1 ^ 3 ^ 5 ) ^ (1 ^ 2 ^ 3 ^ 4 ^ 5) - As per the property of XOR, the same elements will cancel out, and we will be left with 2 XOR 4 = 6 (110). But we don’t know the exact numbers. Let them be A and B.
- A bit is set in xor only if corresponding bits in A and B are different. This is the crucial step to understand.
- We take a set bit in XOR. Let us consider the rightmost set bit in XOR, setBit = 010.
- If we XOR all the elements of arr[] and 1 to ‘N’ with the rightmost bit set, we will get one of the repeating numbers, say x.

Ex: Elements in arr[] with bit set: {3} - Elements from 1 to n with bit set {2, 3}
- The result of XORing all these is A = 2.

- Similarly, if we XOR all the elements of arr[] and 1 to n that have the rightmost bit not set, we will get the other element, say B.

Ex: Elements in arr[] with bit not set: {1, 5}. - Elements from 1 to n with bit not set {1, 4, 5}
- The result of XORing all these is B = 4.

- Hence we found A = 2 and B = 4.

SIMILAR PROBLEMS

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy

# Vertical Sum in BST

Posted: 27 Jul, 2021

Difficulty: Moderate

# Remove K Corner Elements

Posted: 31 Jul, 2021

Difficulty: Easy

# Wildcard Queries

Posted: 31 Jul, 2021

Difficulty: Hard

# Subset OR

Posted: 31 Jul, 2021

Difficulty: Moderate