wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> find the 2 non-repeating numbers
        
(Message started by: inexorable on Oct 24^th, 2007, 2:28pm)

Title: find the 2 non-repeating numbers
Post by inexorable on Oct 24^th, 2007, 2:28pm

Given an array of integers where each number occurs twice except two which occur only once each. Find both non-repeating numbers in O(n) time using O(1) space.

Title: Re: find the 2 non-repeating numbers
Post by towr on Oct 24^th, 2007, 2:37pm

[hide]xor the array, note a bit on which the two numbers differ, split the array on said bit, xor both subarrays; done.[/hide]

Title: Re: find the 2 non-repeating numbers
Post by inexorable on Oct 24^th, 2007, 3:38pm

Can this be extended to an arbitrary number of unknowns instead of 2? if so what would be the complexity then?

Title: Re: find the 2 non-repeating numbers
Post by towr on Oct 25^th, 2007, 2:25am

on 10/24/07 at 15:38:44, inexorable wrote:

Can this be extended to an arbitrary number of unknowns instead of 2? if so what would be the complexity then?

Not as it is, because three different numbers might xor to 0. (e.g. take 1, 2 and 3)
So you'd have to find another way to split up the array; perhaps use xor of squares as well, or just split on every bit at the start.

Title: Re: find the 2 non-repeating numbers
Post by gowrikumar on Oct 25^th, 2007, 5:43am

on 10/24/07 at 14:37:17, towr wrote:

[hide]xor the array, note a bit on which the two numbers differ, split the array on said bit, xor both subarrays; done.[/hide]

@towr:
I couldn't understand the logic. Could you explain this a bit more (preferably with code)?

Regards,
Gowri Kumar

Title: Re: find the 2 non-repeating numbers
Post by towr on Oct 25^th, 2007, 6:14am

on 10/25/07 at 05:43:08, gowrikumar wrote:

@towr:
I couldn't understand the logic. Could you explain this a bit more (preferably with code)?

If you xor all the elements from the array together, then all the doubles cancel each other out. So you are left with the xor of the two distinct elements. Which means that every 1-bit is one on which they differ. Pick any position where you have a 1-bit, then take the xor of all elements that have that bit set, and the xor of the elements that don't have it set. The doubles cancel out again, so you get the two distinct numbers.

Code:

// xor all elements together
tmp=0;
for(int i=0; i < N; i++)
tmp ^= arr[i];

// find highest order bit (assuming 32 bit unsigned integers)
// there must be one, since we have the xor of two distinct numbers
tmp |= tmp >> 1;
tmp |= tmp >> 2;
tmp |= tmp >> 4;
tmp |= tmp >> 8;
tmp |= tmp >> 16;
tmp++;
tmp >>= 1;

// find the two numbers
num1=num2=0;
for(int i=0; i < N; i++)
if (arr[i] & tmp)
num1 ^= arr[i];
else
num2 ^= arr[i];

Title: Re: find the 2 non-repeating numbers
Post by Aryabhatta on Oct 25^th, 2007, 9:59am

This has appeared before I think:

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1177258305

Title: Re: find the 2 non-repeating numbers
Post by Mr.Unknown on Oct 26^th, 2007, 2:57pm

We can use [hide] x & (-x) [/hide] to isolate the set least significant bit .

This would even make the code independent of integer size.

Instead of -x, we can use ( ~x + 1).

Code:

#include<stdio.h>
int main()
{
int n;
scanf("%d",&n);

int a[n];
int i;
for(i=0;i<n;i++)
scanf("%d",&a[i]);

int i,xorofall=0;
for(i=0;i<n;i++)
xorofall^=a[i];

int bit_set;
bit_set=(xorofall)&(-xorofall);

int first=0,second=0;
for(i=0;i<n;i++)
{
if(bit_set&a[i])
{
first^=a[i];
}
else
{
second^=a[i];
}
}

printf("%d %d\n",first,second);
}

Title: Re: find the 2 non-repeating numbers
Post by towr on Oct 26^th, 2007, 3:03pm

on 10/26/07 at 14:57:41, Mr.Unknown wrote:

We can use [hide] x & (-x) [/hide] to isolate the set least significant bit .

This would even make the code independent of integer size.

It's also a fair bit shorter; nice improvement.

Title: Re: find the 2 non-repeating numbers
Post by mganesh on Oct 29^th, 2007, 2:43am

@ Mr.Unknown

One small correction in the above code.

bit_set=(xorofall)^(-xorofall);

The above line should have been as below:
bit_set=(xorofall)&(-xorofall);

Instead of using '&' it was '^' . I hope this is just a typo mistake. 8)

Title: Re: find the 2 non-repeating numbers
Post by Mr.Unknown on Oct 29^th, 2007, 4:15am

yea .. that was a typo ..
Thanks for the correction.