/*
A compiling version of Atamurad's code
*/
#include <iostream>
using namespace std;
int oddman(int a[], int n)
{
int res=0;
for(int i=0;i<n;i++)
{
res^=a[i];
}
return res;
}
int main()
{
int a[5]={2,3,4,3,2};
cout<<oddman(a,5);
return 0;
}
On 1/16/07, Atamurad Hezretkuliyev <[EMAIL PROTECTED]> wrote:
> I am not sure how XOR will be defined on numbers.
Let X be number which occurs only once in sequence.
and i1, i2 are same, ie i1=i2. where i is one of a, b, c, ...
Let X, a1, a2, b1, b2, c1, c2... be input seuqnce then
Then,
res = X XOR a1 XOR a2 XOR b1 XOR b2 XOR c1 XOR c2 XOR .....
is (because i1=i2)
res = X XOR a1 XOR a1 XOR b1 XOR b1 XOR c1 XOR c1 XOR .....
and a xor b xor b = a so
res = X XOR b1 XOR b1 XOR c1 XOR c1 XOR .....
res = X
As you see, if we XOR all numbers, only X leaves as result, which
occurs only once in seuqnce. Main point here is that XOR-in twice with
same number leaves original value.
Here is pseudocode
for(int i=0; i<n; i++)
res = res xor seq[i]
output res
Time O(n), Memory O(1)
http://en.wikipedia.org/wiki/Xor
>
--~--~---------~--~----~------------~-------~--~----~
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 [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
