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.

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