Odd Occurence¶

Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.

XOR¶

As XOR of 2 identical element is zero, hence all the even ones cancel out each other

In [1]:

def oddOccur(arr):
    res = 0
    
    for a in arr:
        res ^= a
        
    return res

In [2]:

arr = [2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2]
arr

Out[2]:

[2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2]

In [3]:

oddOccur(arr)

Out[3]:

Using Reduce and XOR¶

In [4]:

from functools import reduce

In [5]:

reduce(lambda x, y: x ^ y, [1, 1, 2, 2, 3])

Out[5]: