Problem solving with programming: Finding the missing element in an array:

Problem solving with programming: 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

Read full article from Problem solving with programming: Finding the missing element in an array: