Can you give the answer

Discussion in 'C' started by debleena_doll2002, Sep 5, 2008.

  1. debleena_doll2002

    debleena_doll2002 New Member

    Joined:
    Feb 5, 2008
    Messages:
    119
    Likes Received:
    0
    Trophy Points:
    0
    Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.

    It should be efficient way. means If you can then do it in O(n)
     
  2. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Try doing it on paper first. What numbers are missing from { 5 2 8 1 10 3 7 4 }?
    How did you work it out? OK, if you looked for 1, then 2, then 3 etc, that's inefficient. Work it out again starting at the first element in the array, looking at each element only once.

    Hint: You can take notes. For example, how might you keep track of the fact that you've seen a 5 after processing the first element?
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice