Home > Algorithms, Computer Programming, Computer Science > Just Another Programming Puzzle (Finding one non repeating element in list of pairs)

Just Another Programming Puzzle (Finding one non repeating element in list of pairs)

So here is a programming question once again,

Consider a list of unsorted positive numbers in which each number has a pair except one of the number, the problem is to find that number in minimum complexity with O(1) extra space. The complexity in this case should not be more than O(n).

For instance, in the list {5,7,4,9,5,7,4} the answer should be 9. I will post my solution in the comments some time later.

Advertisements
  1. March 12, 2008 at 7:44 am

    The solution is as follows remember the list is not sorted,

    FACT 1: XORing a number with 0 will return the number itself.

    FACT 2: XORing a number with itself will return 0.

    So when we XOR all the elements with each other in a list of number in which each number is repeated once except one number we will get the non repeated number. For example if List is {5,4,6,4,5} we will get 6 if we execute this: 5 XOR 4 XOR 6 XOR 4 XOR 5.

    Here is the C Sharp Source to do the same.

    int Foo(int [] nList)
    {
    int result = 0;
    for (int i = 0; i < nList.Length; i++)
    result ^= nList[i];
    return result;
    }

    In C Sharp ‘^’ is the operator for XOR, This piece of code takes O(n) time and O(1) extra space.

  2. March 12, 2008 at 7:13 pm

    I think a little bit modification require …

    result ^= nList[i]

  3. March 12, 2008 at 7:16 pm

    and what about make it little bit more efficient …

    int Foo(int [] nList)
    {
    int result = nList[0]; // we know the first element
    for (int i = 1; i < nList.Length; i++) // running one less than total numbers
    result ^= nList[i];

    return result;
    }

  4. March 12, 2008 at 7:51 pm

    Ohh well Qasim Pasta!! there was a typo, ammended it.. :), well I dont think capturing the first element and running the loop n – 1 times will make any difference, though your comment and intention noted :)…

    Thx for poiting out the typo..

  5. Hisham abd El-Hafez
    April 2, 2008 at 4:31 pm

    ok, I have another solution

    Fact: all of list elements has another element equivalent except for one element, which means that list length is an odd number

    if you start from the beginning the list and add the numbers to each other, until you reach the middle number, then you start subtracting numbers from the total until you are done, then the final count will be the number with no corresponding peer

    int Foo(int[] arr)
    {
    int count = arr[0];
    for(int i = 0; i < arr.Length; i++)
    {
    if( i <= (size – 1) / 2)
    count += arr[i];
    else
    count -= arr[i];
    }
    return count;
    }

  6. san
    April 5, 2008 at 5:57 am

    Create Map

    Loop thru your array and check

    if elememt in aaray exist in map , if not then add

    if exists then remove

    Finally only one element will left will be your non repeated elemet.

  7. Hisham abd El-Hafez
    April 6, 2008 at 7:43 am

    san, the problem definition states that you should solve it in O(1) extra space, using your map, the extra space complexity will be O(n-1)

  8. Vinayak
    April 30, 2008 at 1:21 pm

    @ Hisham abd El-Hafez:

    Actually your solution works only if the pairs are quasi symmetrically placed and if your pairless number is not the center number then you end up performing the same operation on both the numbers of atlease 1 pair;
    eg: 4 4 5 7 5
    according to your solution we actuallly have

    4 + 4 + 5 – 7 – 5 = 1

  9. Hisham abd El-Hafez
    May 12, 2008 at 1:30 pm

    Vinayak,
    Yeah you are right, my solution will only work if the array is symmetric.
    my mistake 🙂

  10. Arthur Rodrigues
    August 2, 2008 at 1:24 pm

    By the way.. Let’s manually run the proposed algorithm for the following list: ( 4,5,4,7,5 )

    (4 ^ 5) ^ 4 ^ 7 ^ 5

    ( 0 ^ 4 ) ^ 7 ^ 5

    (4 ^ 7 ) ^ 5

    0 ^ 5 = 5 .. and 5 is not the non repeating element….

  11. yashez
    September 10, 2008 at 2:04 am

    @Arthur Rodrigues:

    (4 ^ 5) = 1, and it works

  12. Owen
    September 12, 2008 at 1:08 am

    The proposed algorithm clearly does not work.

    if the list is [5, 4, 6, 4, 5]

    then,

    result = (((5 XOR 4) XOR 6) XOR 4) XOR 5
    = (( 0 XOR 6) XOR 4) XOR 5
    = (6 XOR 4) XOR 5
    = 0 XOR 5
    = 5

    Perhaps I’ve misunderstood ?

    There’s an intuitive solution to this problem, based on quick sort. It’s O (n log n) though

    Pick an element at random, the pivot, and then move the elements less than this number into one set and the elements greater into another set.

    If your two sets are of equal size, then stop and return the pivot.

    Repeat on the list that has an odd size.

    • raj
      July 31, 2011 at 7:59 am

      @Owen: 5^4!=0 ……..5^4=1

  13. Owen
    September 12, 2008 at 1:10 am

    Sorry

    scratch that, I haven’t had my morning coffee

    Just sort O (n log n) then scan through (O (n))

  14. Owen
    September 12, 2008 at 1:13 am

    Actually,

    My original algorithm will work and will be slightly faster than quick sort because you only recurse down a fraction of the tree.

    But, it’s still not linear time.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: