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