# 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;}`