@Tech: I'm not sure I understand your algorithm. Let's try it on
{1,1,2,2,3,4,5,5,6,6,7,7}. The two number occurring an odd number of
times are 3 and 4. We xor the numbers getting 7 = 111 in binary. Now
how do we divide the numbers into two groups?
Dave
On Aug 26, 11:09 am, tech coder
I believe this is what techcoder is saying:
int a[N];
// Find the bitwise xor of all the array values.
// These are the bits which are different between the two results.
int xor = 0;
for(i = 0; i N; ++i)
xor ^= a[N];
// Find the low order bit of xor
int bit = 1;
while(!(xor bit))
bit = 1;
XOR all the elements in the array, the result will be the XOR of the two
numbers occuring odd number of times.
Now take any set bit of th result(u can determine the position of any bit
set in the number). Divide the array such that for the numbers for which at
this location(where the bit is set
@Tech, Don: How about this: given n and array a[n]:
int x = 0, result[2] = {0};
for( i = 0 ; i n ; ++i )
x ^= a[i];
x |= x(x-1); // low order 1-bit of xor
for( i = 0 ; i n ; ++i )
result[a[i]x?0:1] ^= a[i];
Dave
On Aug 26, 12:49 pm, Don dondod...@gmail.com wrote:
I believe this is
@Tech: I'm not sure I understand your algorithm. Let's try it on
{1,1,2,2,3,4,5,5,6,6,7,7}. The two number occurring an odd number of
times are 3 and 4. We xor the numbers getting 7 = 111 in binary. Now
how do we divide the numbers into two groups?
see we come to know that both number differ at
@ Don exactly waht u write i wanted to say
On Fri, Aug 26, 2011 at 11:52 AM, tech coder techcoderonw...@gmail.comwrote:
@Tech: I'm not sure I understand your algorithm. Let's try it on
{1,1,2,2,3,4,5,5,6,6,7,7}. The two number occurring an odd number of
times are 3 and 4. We xor the numbers
@don really cool algo man
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options,
@Sachin: You can sort the array in O(n log n), and then finding the
two numbers is an additional O(n), so the resulting complexity is O(n
log n).
Dave
On Aug 25, 2:01 pm, sachin sabbarwal algowithsac...@gmail.com wrote:
We have an array which contains integer numbers (not any fixed range). Only
