Find Odd Singleton
by Isai Damier

#======================================================================
# 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 ) )