Find missing number

Problem description:

You have an array A of size n – 1 containing numbers from 1 to n so there is one missing number, find it!

First Approach using extra memory:

We could create a boolean array B of size n + 1 and set to true the index of every number found in A, at the end our boolean array will have only one element in false, that’s the missing number.

int findMissingNumber(int A[], int n)
{
	boolean B[] = new boolean[n + 1];
	for(int i = 0; i < A.length; ++i)
		B[A[i]] = true;
	
	int missing = 0;
	for(int i = 1; i < B.length; ++i)
		if(!B[i]) missing = i;
	
	return missing;
}

Second Approach without extra memory:

Another approach that avoids the use of extra memory is to sum up all the elements in the array and subtract that value from the total sum which can be obtained with the following formula (n * (n + 1)) / 2

int findMissingNumber(int A[], int n)
{
	int total = (n * (n + 1)) / 2;
	int sum = 0;
	for(int i = 0; i < A.length; ++i)
		sum += A[i];
	
	return total - sum;
}

This solution only uses constant space but the problem is that if the numbers are too large we could overflow the variable sum since an integer has a max value.

Third approach, XOR:

This approach is based on the XOR operation, remember:

A B | A XOR B
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

so:
A ^ 0 = A
A ^ A = 0
A ^ B = C
C ^ A = B

The key is to realize that if we XOR the same number twice we are gonna get 0 (equal numbers are removed), but if we XOR a number once then this number is kept, so we can XOR all numbers from 1 to n and then xor all numbers in our array, at the end we are gonna have the missing number since all duplicated numbers were removed, here the code:

int findMissingNumber(int A[], int n)
{
	int xor = 0;
	for(int i = 1; i <= n; ++i)
		xor ^= i;
		
	for(int i = 0; i < A.length; ++i)
		xor ^= A[i];
	
	return xor;
}

This solution doesn’t have the problem of integer overflow like the previous one and needs only linear time and constant space 🙂

Advertisements