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.