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;

}