Find the two numbers with odd occurrences in an unsorted array | Prints two numbers that occur odd number of times . The function assumes that the array size is at least 2 and there are exactly two numbers occurring odd number of times . ; Will hold XOR of two odd occurring elements ; Will have only single set bit of xor2 ; Get the xor of all elements in arr [ ] . The xor will basically be xor of two odd occurring elements ; Get one set bit in the xor2 . We get rightmost set bit in the following line as it is easy to get ; Now divide elements in two sets : 1 ) The elements having the corresponding bit as 1. 2 ) The elements having the corresponding bit as 0. ; XOR of first set is finally going to hold one odd occurring number x ; XOR of second set is finally going to hold the other odd occurring number y ; Driver Code
def printTwoOdd ( arr , size ) : NEW_LINE INDENT xor2 = arr [ 0 ] NEW_LINE set_bit_no = 0 NEW_LINE n = size - 2 NEW_LINE x , y = 0 , 0 NEW_LINE for i in range ( 1 , size ) : NEW_LINE INDENT xor2 = xor2 ^ arr [ i ] NEW_LINE DEDENT set_bit_no = xor2 & ~ ( xor2 - 1 ) NEW_LINE for i in range ( size ) : NEW_LINE INDENT if ( arr [ i ] & set_bit_no ) : NEW_LINE INDENT x = x ^ arr [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT y = y ^ arr [ i ] NEW_LINE DEDENT DEDENT print ( " The ▁ two ▁ ODD ▁ elements ▁ are " , x , " & " , y ) NEW_LINE DEDENT arr = [ 4 , 2 , 4 , 5 , 2 , 3 , 3 , 1 ] NEW_LINE arr_size = len ( arr ) NEW_LINE printTwoOdd ( arr , arr_size ) NEW_LINE