Python: Using XOR operator find unique elements in array

Problem:- Consider an array of  integers, , where every element in  occurs exactly twice except for one unique element.Find and print the unique element.

Input :- 4 9 95 93 57 4 57 93 9 #Input array with 95 as unique element.

Output
:- 95

Background of XOR operator ( ^ ) :-  Bit-wise operator which results zero, if XOR operator is applied between same bits otherwise gives 1.
XOR Operator operation 
We can use XOR operation to reset all bit for two numbers , if they are same.  i.e : 3 ^ 3 = 0

Sample program to print unique element using XOR :-

#!/bin/python

def lonely_integer(a):
    storage = a[0]
    for i in range(1, a.__len__()):
        storage = storage ^ a[i]
    #print (storage)
    return storage
print "Enter size of array (Input) "
n = int(raw_input().strip())
print "Enter elements separated by space "
a = map(int,raw_input().strip().split(' '))
print "Unique element is "
print lonely_integer(a)

Sample output:-
>>>
Enter size of array (Input)
9
Enter elements separated by space
4 9 95 93 57 4 57 93 9
Unique element is
95

1 Comments

Previous Post Next Post