Monday, October 20, 2014

Find the Missing Number 1 to n

You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer.

Example:
I/P    [1, 2, 4, ,6, 3, 7, 8]
O/P    5


METHOD 1(Use sum formula)

Algorithm:
1. Get the sum of numbers 
       total = n*(n+1)/2
2  Subtract all the numbers from sum and
   you will get the missing number.
 
Example::
 
total = n*(n+1)/2 = 8*9/2 = 36
sum = 31
 
Missing number = total - sum =  36-31 = 5

No comments:

Post a Comment