Author |
Topic: find the 2 non-repeating numbers (Read 1219 times) |
|
inexorable
Full Member
Posts: 211
|
 |
find the 2 non-repeating numbers
« on: Oct 24th, 2007, 2:28pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: find the 2 non-repeating numbers
« Reply #1 on: Oct 24th, 2007, 2:37pm » |
Quote Modify
|
xor the array, note a bit on which the two numbers differ, split the array on said bit, xor both subarrays; done.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: find the 2 non-repeating numbers
« Reply #2 on: Oct 24th, 2007, 3:38pm » |
Quote Modify
|
Can this be extended to an arbitrary number of unknowns instead of 2? if so what would be the complexity then?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: find the 2 non-repeating numbers
« Reply #3 on: Oct 25th, 2007, 2:25am » |
Quote Modify
|
on Oct 24th, 2007, 3:38pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
GowriKumar
Junior Member
 
Gender:
Posts: 55
|
|
Re: find the 2 non-repeating numbers
« Reply #4 on: Oct 25th, 2007, 5:43am » |
Quote Modify
|
on Oct 24th, 2007, 2:37pm, towr wrote:| xor the array, note a bit on which the two numbers differ, split the array on said bit, xor both subarrays; done. |
|
@towr:
I couldn't understand the logic. Could you explain this a bit more (preferably with code)?
Regards,
Gowri Kumar
|
|
IP Logged |
www.gowrikumar.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: find the 2 non-repeating numbers
« Reply #5 on: Oct 25th, 2007, 6:14am » |
Quote Modify
|
on Oct 25th, 2007, 5:43am, 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];
|
|
|
| « Last Edit: Oct 25th, 2007, 6:15am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Mr.Unknown
Newbie
Posts: 4
|
|
Re: find the 2 non-repeating numbers
« Reply #7 on: Oct 26th, 2007, 2:57pm » |
Quote Modify
|
We can use x & (-x) 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);
}
|
|
|
| « Last Edit: Oct 29th, 2007, 4:16am by Mr.Unknown » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: find the 2 non-repeating numbers
« Reply #8 on: Oct 26th, 2007, 3:03pm » |
Quote Modify
|
on Oct 26th, 2007, 2:57pm, Mr.Unknown wrote:We can use x & (-x) 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mganesh
Newbie
Live your life
Gender:
Posts: 1
|
|
Re: find the 2 non-repeating numbers
« Reply #9 on: Oct 29th, 2007, 2:43am » |
Quote Modify
|
@ 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. 
|
|
IP Logged |
|
|
|
Mr.Unknown
Newbie
Posts: 4
|
|
Re: find the 2 non-repeating numbers
« Reply #10 on: Oct 29th, 2007, 4:15am » |
Quote Modify
|
yea .. that was a typo ..
Thanks for the correction.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print