#======================================================================
# Author: Isai Damier
# Title: Find Odd Float Singleton
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
# Given an array of floating point numbers 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: fArr = [1.2, 7.340, 2.3, 3.34, 7.340, 4.567,
# 5.65, 6.234, 7.340, 4.567, 7.340, 2.3,
# 6.234, 7.340, 3.34, 1.2, 5.65]
# Sample Output: 7.340
#
# Technical Details:
# The most efficient approach is to XOR all the elements of the array
# 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).
#
# However, there is still one problem: Python does not define bitwise
# operations for float. Therefore, the following steps are followed to
# find the singleton:
# 0] Convert each floating point number to virtual
# bits using floatToBits(f), which we also define.
# 1] Perform XOR operation on the values while in virtual bits form.
# 2] Convert the final bits result to float using bitsToFloat( i ).
# 3] Return the final float value.
#
#======================================================================
import struct
def findOddFloatSingleton( a ):
b = floatToBits( a[0] )
for n in range( 1, len( a ) ):
b ^= floatToBits( a[n] )
return bitsToFloat( b )
def floatToBits( n ):
value = struct.pack( '>f', n )
return struct.unpack( '>l', value )[0]
def bitsToFloat( n ):
value = struct.pack( '>l', n )
return struct.unpack( '>f', value )[0]
import unittest
from algorithms import bitwise as bits
class Test( unittest.TestCase ):
def testFindOddSingleton_float( self ):
fList = [1.2, 7.340, 2.3, 3.34, 7.340, 4.567, 5.65, 6.234, 7.340,
4.567, 7.340, 2.3, 6.234, 7.340, 3.34, 1.2, 5.65]
expected = "7.34"
result = "%.2f" % bits.findOddFloatSingleton( fList )
self.assertEqual( expected, result )
