Cracking the Coding Interview: Fourth Edition (308 page e-book / PDF)
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.

7 comments:

  1. Sort the array using quicksort..and check adjacent
    elements..u can know there are duplicates or
    not..complexity-O(nlogn)+n-1

    ReplyDelete
  2. Let s be the sum of the n elements in the array.
    Let s2 be the sum of the numbers from 1 to n+1.

    s2 - s is the number that is missing.

    Complexity O(1).

    ReplyDelete
  3. 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.

    ReplyDelete
  4. We know sum of n+1 elements = ((n+1)*(n+2))/2

    We 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).

    ReplyDelete
  5. The above solution is the correct solution

    ReplyDelete
  6. 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

    ReplyDelete