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 in the result) is set and those where
this bit is not set.
now XOR both the sets, this will give u two numbers,one from each of the two
subsets.
Sanju
:)
On Fri, Aug 26, 2011 at 10:49 AM, Don dondod...@gmail.com wrote:
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 the values with bit set to get one result
// xor the values with bit unset to get the other result
int result1 = 0, result2 = 0;
for(i = 0; i n; ++i)
{
if (a[i] bit) result1 ^= a[i];
else result2 ^= a[i];
}
Now result1 result2 are the values which appear an odd number of
times. It is O(n).
Don
On Aug 26, 12:13 pm, Dave dave_and_da...@juno.com wrote:
@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 techcoderonw...@gmail.com wrote:
it can be done in O(N) by using XOR ing the elements
1: Xor all the elemnts since those elemnts that even freq will nullify
each
other we get number taht will tell in which the two required number
differ.
2: divide the array in two sets on the basis of bit in which numbers
differ
3:1 element will be in one set another will be in another set
4: XOR both the sets again we get both the elemts
On Thu, Aug 25, 2011 at 12:50 PM, Umesh Jayas algowithum...@gmail.com
wrote:
int main()
{
int arr[]={1,2,5,1,5,1,1,3,2,2,};
int elements = sizeof(arr)/sizeof(arr[0]);
int count=1;
int num;
sort(arr,arr+elements);
num=arr[0];
for(int i=1;ielements;i++)
{
if(arr[i]==num)
count++;
else
{
if(count%2==0)
{ num=arr[i];
count=1;}
else
{cout\narr[i-1];
count=1;
num=arr[i];
}
}
}
getch();
}
complexity: O(nlogn)
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text -
- Show quoted text -
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
