Find the repeating and the missing | Added 3 new methods | PHP program to Find the repeating and missing elements ; Will hold xor of all elements and numbers from 1 to n ; Will have only single set bit of xor1 ; Get the xor of all array elements ; XOR the previous result with numbers from 1 to n ; Get the rightmost set bit in set_bit_no ; Now divide elements in two sets by comparing rightmost set bit of xor1 with bit at same position in each element . Also , get XORs of two sets . The two XORs are the output elements . The following two for loops serve the purpose ; arr [ i ] belongs to first set ; arr [ i ] belongs to second set ; i belongs to first set ; i belongs to second set ; * x and * y hold the desired output elements ; Driver Code
< ? php function getTwoElements ( & $ arr , $ n ) { $ xor1 ; $ set_bit_no ; $ i ; $ x = 0 ; $ y = 0 ; $ xor1 = $ arr [ 0 ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) $ xor1 = $ xor1 ^ $ arr [ $ i ] ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) $ xor1 = $ xor1 ^ $ i ; $ set_bit_no = $ xor1 & ~ ( $ xor1 - 1 ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { if ( ( $ arr [ $ i ] & $ set_bit_no ) != 0 ) $ x = $ x ^ $ arr [ $ i ] ; else $ y = $ y ^ $ arr [ $ i ] ; } for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { if ( ( $ i & $ set_bit_no ) != 0 ) $ x = $ x ^ $ i ; else $ y = $ y ^ $ i ; } } $ arr = array ( 1 , 3 , 4 , 5 , 1 , 6 , 2 ) ; $ n = sizeof ( $ arr ) ; getTwoElements ( $ arr , $ n ) ;