@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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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
> > > <[email protected]>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;i<elements;i++)
> > > > {
> > > > if(arr[i]==num)
> > > > count++;
> > > > else
> > > > {
> > > > if(count%2==0)
> > > > { num=arr[i];
> > > > count=1;}
> > > > else
> > > > {cout<<"\n"<<arr[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 [email protected].
> > > > To unsubscribe from this group, send email to
> > > > [email protected].
> > > > For more options, visit this group at
> > > >http://groups.google.com/group/algogeeks?hl=en.-Hidequoted text -
>
> > > - Show quoted text -- 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
