Given you an array of 100 Elements with one number missing, how will you find the missing number?
Ex.: Array 1 to 100 with 55 missing.
Solution:
Just do sum of all the numbers from 1 to 100 : (n * (n+1))/2 and find sum of all the elements from actual array. Just take the difference and you will get missing number.
If numbers start with n > 1, then normalize them by subtracting n-1.
Complexity:
time - O(n)Links and credits:
space - O(1)
http://www.careercup.com/question?id=23092662
See also: Find two missing numbers
No comments:
Post a Comment