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
< ? php function printTwoOdd ( $ arr , $ size ) { $ xor2 = $ arr [ 0 ] ; $ set_bit_no ; $ i ; $ n = $ size - 2 ; $ x = 0 ; $ y = 0 ; for ( $ i = 1 ; $ i < $ size ; $ i ++ ) $ xor2 = $ xor2 ^ $ arr [ $ i ] ; $ set_bit_no = $ xor2 & ~ ( $ xor2 - 1 ) ; for ( $ i = 0 ; $ i < $ size ; $ i ++ ) { if ( $ arr [ $ i ] & $ set_bit_no ) $ x = $ x ^ $ arr [ $ i ] ; else $ y = $ y ^ $ arr [ $ i ] ; } echo " The ▁ two ▁ ODD ▁ elements ▁ are ▁ " , $ x , " ▁ & ▁ " , $ y ; } $ arr = array ( 4 , 2 , 4 , 5 , 2 , 3 , 3 , 1 ) ; $ arr_size = sizeof ( $ arr ) ; printTwoOdd ( $ arr , $ arr_size ) ; ? >