The magic of XOR

Given an array of elements where each element occurs twice except one element, how do you find the element which occurs only once?

Well, the obvious way is to loop through the array and keep track of how many time each element occurs.

But there is an even simpler and faster way to find the required element. The secret lies in the unique property of XOR.

The truth table of XOR is

The output is set only when one of the inputs is 1. This gives rise to some unique results which are very useful.

We will use the symbol ^ to denote XOR, which is used in most programming languages. Let n be any number then,

• n ^ 0 = n
• n ^ n = 0

This means if we XOR all the elements of the array, We will be left with the element which occurs only once since the duplicate elements cancel each other.

Example : 

consider the array 

Python Code :

a = [2,2,3,5,6,5,7,8,8,7,3]

result = 0

for i in a: 

    result ^= i

print(result)

Output : 

Powered by Froala Editor