Delivered instantly as a PDF via email. For Software Engineers & SDETs
150 programming interview questions and answers
5 proven approaches to crack algorithm questions
10 mistakes candidates make, and how to avoid them.
How to prepare for technical and behavioral questions without wasting your time!
"The BEST book for acing your interview. It helped me land my Microsoft job, and it was worth every penny!" - Ravi (Accepted at Microsoft, Amazon and Facebook)
30 Day Money Back Guarantee: Don't love the book? We'll give you your money back!More Info
Saturday, April 24, 2010
Array of size n
Given an array of size n, containing every element from 1 to n+1, except one. Find the missing element.
We can also have an integer initially set to 1. Check this integer value with the first element If match found increment integer++ Else print the current value of integer as missing no break
Sort the array using quicksort..and check adjacent
ReplyDeleteelements..u can know there are duplicates or
not..complexity-O(nlogn)+n-1
Let s be the sum of the n elements in the array.
ReplyDeleteLet s2 be the sum of the numbers from 1 to n+1.
s2 - s is the number that is missing.
Complexity O(1).
Wrong. It is (n+1)-(s2-s). And complexity is O(n) because you have to calculate the sum in s2 by iterating through array.
ReplyDeleteWe know sum of n+1 elements = ((n+1)*(n+2))/2
ReplyDeleteWe iterate through the array and subtract the sum of elements from sum of n+1 elements
The missing value is the missing number. Complexity is O(n).
The above solution is the correct solution
ReplyDeleteWe can also have an integer initially set to 1.
ReplyDeleteCheck this integer value with the first element
If match found
increment integer++
Else
print the current value of integer as missing no
break
abo
ReplyDelete