#======================================================================
# Author: Isai Damier
# Title: Find Odd Singleton
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
# Given a list where all values occur an even number of times;
# except for one value, which occurs an odd number of times and which
# we shall call a singleton; find the singleton.
#
# Sample Input: 1,2,7,3,4,5,7,6,7,4,2,6,3,1,5
# Sample Output: 7
#
# Technical Details:
# The most efficient approach is to XOR all the elements of the list
# and return the result. Recall from digital logic the following
# truths about the XOR (^) operator: x^x = 0; 0^x = x.
# (Ref http://www.teahlab.com/basicGates/xorgate).
#======================================================================
def findOddSingleton( a ):
i = a[0]
for n in range( 1, len( a ) ):
i ^= a[n]
return i
import unittest
from algorithms import bitwise as bits
class Test( unittest.TestCase ):
def testFindOddSingleton_int( self ):
intList = [1, 2, 7, 3, 4, 5, 7, 6, 7, 4, 2, 6, 3, 1, 5]
self.assertEquals( 7, bits.findOddSingleton( intList ) )
