Tuesday, August 4, 2009

find duplicate

You are given an array with integers between 1 and 1,000,000. One integer is in the array twice. How can you determine which one? Can you think of a way to do it using little extra memory?




click here for answer


do a heap sort - in-place algorithm. sorts with O(1) extra space requirements.
traverse through the array finding if the next element is same as the previous element since now the duplicates will be consequetively present.


this is one of the possible answers. if you have a better solution, please post so..
Posted by at
Labels: ,

7 comments:

  1. UnknownAugust 21, 2009 at 3:57 AM

    Calculate n*n+1/2 and subtract it from the sum of array.

    ReplyDelete
  2. SujathaAugust 27, 2009 at 8:16 AM

    sudha,
    cool. your method uses O(n)in all cases with no extra memory. nice answer.

    ReplyDelete
  3. karthikAugust 27, 2009 at 9:25 PM

    1,2,4,1,5 - sum 13

    5 * 6/2 = 15

    13 - 15 = -2

    are u missing -2

    wrong solution..

    ReplyDelete
  4. UnknownAugust 27, 2009 at 10:43 PM

    @karthik mm. either you missed a 3 in that array or i comprehended the question wrong. I assumed all the numbers being there

    If what you had said is the case then sort + fetch as suja suggested would give the best result.

    ReplyDelete
  5. karthikAugust 27, 2009 at 11:50 PM

    yeah...assigning it back to questioner to provide clear, unambigous questions..:)

    ReplyDelete
  6. SujathaAugust 28, 2009 at 7:15 AM

    karthik, sudha,
    to clarify... the question clearly says one integer is present twice. it does not state anything about finding missing integers.

    ReplyDelete
  7. KarthikSeptember 10, 2009 at 9:46 PM

    yikes...ok,right question

    ReplyDelete

Subscribe to: Post Comments (Atom)