Home Arrays Find the missing number in an array. (Method 4)

Find the missing number in an array. (Method 4)

by nikoo28
0 comment

Question:- We are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing. Give an algorithm to find the missing integer.

Input:- 1, 2, 4, 6, 3, 7, 8
Output:- 5

We solved this problem using array summation here. We can also utilize the property of XOR to solve this problem. The major property of XOR that we will be using is A XOR A = 0.

Thus, the steps involved are:-

  • XOR all the numbers from 1 to n. Get a value ‘num1’.
  • XOR all the elements of the array. Get a value ‘num2’.
  • Get the XOR of num1 and num2.

Since all the elements are repeated, the XOR becomes 0 and the only numbers that does not becomes zero is the missing number. Thus we get our number. Here is an implementation of the algorithm:-

//find missing number in array of size 'size' range is 1-n
int findMissingNumberXOR(int arr[], int size, int n)
{
	int i;

	int xor1 = 0;
	//get the XOR of all the numbers from 1 to n
	for(i=1;i<=n;i++)
		xor1 ^= i;

	int xor2 = 0;

	//loop through the array and get the XOR of elements
	for(i = 0;i<size;i++)
	{
		xor2 ^= arr[i];
	}

	return (xor1 ^ xor2);
}

Time Complexity:- O(n) to scan the array
Space Complexity:- O(1)

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More