• RSS
  • Facebook
  • Twitter

Knowledge is Power.

  • Who you are ?

    Working on machines without understanding them ? Then you should be here..

  • Where you are ?

    Geographical location should not become a barrier to Share our knowledge.

  • What do you do ?

    Puzzles and Interview question are intended to be discussed here.

    Thursday, February 25, 2010

    Given an array of m+n elements in the range 1 to n ie(m elements are repeated). Find the duplicate elements.
    Time Complexity: O(m+n)
    Space Complexity: O(m)

    Solution :

    Since we know there are 1 to n elements, we can sort the array in O(n).
    The first n elements will be the unique values and n to m will be the duplicates.
    This is O(n+m) && no extra space required.

    for (int i = 0; i < array.Length; i++)
    {
    if (array[i] != i + 1)
    {
    int t = array[array[i]-1];
    array[array[i]-1] = array[i];
    array[i] = t;
    }
    }

    0 comments:

    Post a Comment