Last Updated: 1 Mar, 2021
Find Two Missing Numbers
Moderate
Asked in companies
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.
Approaches
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.
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.