Find the repeating and the missing | Added 3 new methods | The output of this function is stored at x and y ; Will hold xor of all elements and numbers from 1 to n ; Get the xor of all array elements ; XOR the previous result with numbers from 1 to n ; Will have only single set bit of xor1 ; Now divide elements into two sets by comparing a rightmost set bit of xor1 with the bit at the 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 ; Driver code
def getTwoElements ( arr , n ) : NEW_LINE INDENT global x , y NEW_LINE x = 0 NEW_LINE y = 0 NEW_LINE xor1 = arr [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT xor1 = xor1 ^ arr [ i ] NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT xor1 = xor1 ^ i NEW_LINE DEDENT set_bit_no = xor1 & ~ ( xor1 - 1 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] & set_bit_no ) != 0 : NEW_LINE INDENT x = x ^ arr [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT y = y ^ arr [ i ] NEW_LINE DEDENT DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( i & set_bit_no ) != 0 : NEW_LINE INDENT x = x ^ i NEW_LINE DEDENT else : NEW_LINE INDENT y = y ^ i NEW_LINE DEDENT DEDENT DEDENT arr = [ 1 , 3 , 4 , 5 , 5 , 6 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE getTwoElements ( arr , n ) NEW_LINE print ( " The ▁ missing ▁ element ▁ is " , x , " and ▁ the ▁ repeating ▁ number ▁ is " , y ) NEW_LINE