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.

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.
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;
//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++)

//deallocate dynamic memory
delete[] array;
return 0;