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