OLOLO spoj: The power of Xor

In OLOLO problem of spoj we are required to find the one unique element of the list. The problem specifies that all other elements of the list appear twice. If you haven't read the problem here is the link to this problem OLOLO problem. Please read the problem before reading further.

There can be many approaches to solve this problem.

One approach could be to sort the list of numbers and then see which number does not occur twice. This would be O(nlogn) solution. But as the range of numbers is large and time limit is too short, this is not a good approach. The time limit clearly says that it needs a O(n) solution.

This problem can be solved in O(n) time and O(1) space using the power of XOR.

Let us first look at what Xor does when applied to two numbers.

Suppose I have two numbers 1 and 8. The binary representation of

1 = 00000001 

and

8 = 00001000

Now if i perform xor of both numbers say 

x  = 1 ^ 8

   00000001

^ 00001000

         00001001 = 9

Remember the Xor of two bits is 1 when both bits are different and 0 otherwise. So if we perform Xor of two same numbers, the result will be 0. And this is the property that we can use to solve this problem. That is if we perform Xor of all the numbers in the list, all the numbers which appear even number of times gets cancelled and only the unique number remains.

So let us consider the example test case given in the problem.
n = 3
numbers are : 1 8 1

Let result store the Xor of all the numbers.

Initially

result = 1 ^ 8 = 00000001 ^ 00001000 = 000010001 = 9

Then

result = result ^ 1 = 9 ^ 1 = 000010001 ^ 00000001 = 00001000 = 8

which is our answer.

Here is my C code to this problem: