Find Two Missing Numbers
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

Question

Find Two Missing Numbers

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.

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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.

Time Complexity: O(n)Explanation:

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

C++ (g++ 5.4)

/*

	Time Complexity : O(N)

	Space Complexity : O(N)



	Where N is the size of array.

*/



vector findMissingNumbers(vector &arr, int n)

{

	// visited will check which number are present in array.

	vector visited(n + 1, false);

	for (int i = 0; i < n - 2; i++){

		visited[arr[i]] = true;

	}



	vector res ;



	for (int i = 1; i <= n; i++) {

		if (!visited[i]) {

			res.push_back(i) ;

		}

	}

	return res;

}

Java (SE 1.8)

/*
	Time Complexity : O(N)
	Space Complexity : O(N)

	Where N is the size of array.
*/

import java.util.ArrayList;

public class Solution {
	public static ArrayList findMissingNumbers(ArrayList arr, int n) {
		// Visited will check which number are present in array.
		boolean[] visited = new boolean[n + 1];

		for (int i = 0; i < n - 2; i++) {
			visited[arr.get(i)] = true;
		}

		ArrayList res = new ArrayList<>();

		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				res.add(i);
			}
		}
		return res;
	}
}

Python (3.5)

"""

	Time Complexity : O(N)

	Space Complexity : O(N)



	Where N is the size of array.

"""





def findMissingNumbers(arr, n):



    # visited will check which number are present in array.

    visited = [False] * (n + 1)

    for i in arr:

        visited[i] = True



    res = []



    for i in range(1, n + 1):

        if not visited[i]:

            res.append(i)



    return res

Accepted Answer

Use Bitwise XOR

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.

Space Complexity: O(1)Explanation:

O(1).

Since we are not using any extra space.

Time Complexity: O(n)Explanation:

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

Python (3.5)

"""

	Time Complexity : O(N)

	Space Complexity : O(1)



	Where N is the size of the array.

"""





def findMissingNumbers(arr, n):

    xorSum = arr[0]



    for i in range(1, n - 2):

        xorSum ^= arr[i]



    for i in range(1, n + 1):

        xorSum ^= i



    """	

        Now xorSum has xorSum of two missing elements. Any set

        bit in it must be set in one missing and unset in

        other missing number

    """



    setBits = xorSum & ~(xorSum - 1)



    """

        Now divide elements in two sets by comparing rightmost set bit of xorSum

        with bit at same position in each element.

    """

    firstPart, secondPart = 0, 0



    for i in range(n - 2):

        if arr[i] & setBits:

            firstPart = firstPart ^ arr[i]

        else:

            secondPart = secondPart ^ arr[i]



    for i in range(1, n + 1):

        if i & setBits:

            firstPart = firstPart ^ i

        else:

            secondPart = secondPart ^ i



    if firstPart > secondPart:

        firstPart, secondPart = secondPart, firstPart



    res = []

    res.append(firstPart)

    res.append(secondPart)



    return res

Java (SE 1.8)

/*
	Time Complexity : O(N)
	Space Complexity : O(1)

	Where N is the size of the array.
*/

import java.util.ArrayList;

public class Solution {
	public static ArrayList findMissingNumbers(ArrayList arr, int n) {
		int xorSum = arr.get(0);

		for (int i = 1; i < n - 2; i++) {
			xorSum ^= arr.get(i);
		}

		for (int i = 1; i <= n; i++) {
			xorSum ^= i;
		}

		/*
		 * Now xorSum has xorSum of two missing elements. Any set bit in it must be set
		 * in one missing and unset in other missing number
		 */
		int setBits = xorSum & ~(xorSum - 1);

		/*
		 * Now divide elements in two sets by comparing rightmost set bit of xorSum with
		 * bit at same position in each element.
		 */
		int firstPart = 0, secondPart = 0;

		for (int i = 0; i < n - 2; i++) {
			if ((arr.get(i) & setBits) > 0) {
				firstPart = firstPart ^ arr.get(i);
			} else {
				// XorSum of second set
				secondPart = secondPart ^ arr.get(i);
			}
		}

		for (int i = 1; i <= n; i++) {
			if ((i & setBits) > 0) {
				firstPart = firstPart ^ i;
			} else {
				secondPart = secondPart ^ i;
			}
		}

		if (firstPart > secondPart) {
			int temp = firstPart;
			firstPart = secondPart;
			secondPart = temp;
		}

		ArrayList res = new ArrayList<>();
		res.add(firstPart);
		res.add(secondPart);

		return res;
	}
}

C++ (g++ 5.4)

/*

	Time Complexity : O(N)

	Space Complexity : O(1)



	Where N is the size of the array.

*/



vector findMissingNumbers(vector &arr, int n)

{

	int xorSum = arr[0];



	for (int i = 1; i < n - 2; i++) {

		xorSum ^= arr[i];

	}



	for (int i = 1; i <= n; i++) {

		xorSum ^= i;

	}



	/*	

	 *Now xorSum has xorSum of two missing elements. Any set

	 *bit in it must be set in one missing and unset in

	 *other missing number

	 */



	int setBits = xorSum & ~(xorSum - 1);



	/*

	 *Now divide elements in two sets by comparing rightmost set bit of xorSum

	 *with bit at same position in each element.

	 */

	int firstPart = 0, secondPart = 0;



	for (int i = 0; i < n - 2; i++) {

		if (arr[i] & setBits) {

			firstPart = firstPart ^ arr[i];

		}

		else {

			secondPart = secondPart ^ arr[i];

		}

	}



	for (int i = 1; i <= n; i++) {

		if (i & setBits) {

			firstPart = firstPart ^ i;

		}

		else {

			secondPart = secondPart ^ i;

		}

	}



	if (firstPart > secondPart) {

		swap(firstPart, secondPart) ;

	}



	vector res ;

	res.push_back(firstPart) ;

	res.push_back(secondPart) ;



	return res ;

}

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 :

Input Format :

Output Format :

Note :

Constraints :

Note :

Top Paxcom India Software Developer interview questions & answers

Popular interview questions of Software Developer