Finding the missing element in an array:

An array of size (n-1) contains all the numbers in the range [1..n] except one number which is missing. Write a program to find the missing number in O(n) time and O(1) space.

For example let N= 5 and the input array is [1,3,4,5], the output should be 2.

Given O(n) space we can always maintain a boolean array of size n to store a flag for each number if it is present or not. Here the restriction is to use constant extra space.

Two methods are discussed here.

Method#1:
Find sum of all the elements in given array. Let it be sum1. Find the sum of numbers from 1 to n. It would be n*(n+1)/2 (remember Arithmetic Progression from your school mathematics?) let it be sum2. Now subtracting sum1 from sum2 ( sum2-sum1) gives the required result.
Method#2:
Find XOR of all the elements in the array, let it be ax. Find XOR of elements from [1..n], let it be nx. Then performing XOR between these two gives the missing number

The following C++ code shows the implementation of both the methods stated above. Both algorithms run in O(n) time and O(1) space complexity.

#include <iostream>
using namespace std;
//array contains n-1 numbers, this method finds
//the nth number missing.
int findMissingNum(int *array, int n)
{
 //sum of first n numbers 1...n
 int nSum = n*(n+1)/2;
 //find array sum
 int arSum = 0;
 for( int i = 0 ; i < n-1 ; i++)
 {
  arSum += array[i];
 }
 // difference between two sum, gives the missing number
 return nSum - arSum;
}

int findMissingNumXor(int *array,int n)
{
 int nXor; //XOR of 1..N elements
 int arXor; //XOR of array elements
 int i;
 //find XOR of 1 to n elements
 for( i = 0 ; i < n ;i++)
 {
  nXor = nXor ^ (i+1);
 }
 //find XOR of array elements
 for( i = 0 ; i < n-1 ; i++)
 {
  arXor = arXor ^array[i];
 }
 //XOR of two gives the result
 return nXor ^arXor;
}
int main()
{
 int *array;
 int n;
 cin>>n;
 //allocate memory for n-1 numbers
 array = new int[n-1];
 int i;
 //read n-1 numbers as input
 for( i = 0; i < n-1; i++)
 {
  cin>>array[i];  
 }
 
 cout<<findMissingNumXor(array,n);
 //deallocate dynamic memory
 delete[] array;
 return 0;
}

Leave a Reply Cancel reply