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;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 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.
