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

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

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

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