Find Two Missing Numbers | Set 2 ( XOR based solution ) | Function to find two missing numbers in range [ 1 , n ] . This function assumes that size of array is n - 2 and all array elements are distinct ; Get the XOR of all elements in arr [ ] and { 1 , 2 . . n } ; Get a set bit of XOR ( We get the rightmost set bit ) ; Now divide elements in two sets by comparing rightmost set bit of XOR with bit at same position in each element . ; XOR of first set in arr [ ] ; XOR of second set in arr [ ] ; XOR of first set in arr [ ] and { 1 , 2 , ... n } ; XOR of second set in arr [ ] and { 1 , 2 , ... n } ; Driver program to test above function ; Range of numbers is 2 plus size of array
def findTwoMissingNumbers ( arr , n ) : NEW_LINE INDENT XOR = arr [ 0 ] NEW_LINE for i in range ( 1 , n - 2 ) : NEW_LINE INDENT XOR ^= arr [ i ] NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT XOR ^= i NEW_LINE DEDENT set_bit_no = XOR & ~ ( XOR - 1 ) NEW_LINE x = 0 NEW_LINE y = 0 NEW_LINE for i in range ( 0 , n - 2 ) : 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 for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if i & set_bit_no : NEW_LINE INDENT x = x ^ i NEW_LINE DEDENT else : NEW_LINE INDENT y = y ^ i NEW_LINE DEDENT DEDENT print ( " Two Missing Numbers are % d % d " % ( x , y ) ) NEW_LINE DEDENT arr = [ 1 , 3 , 5 , 6 ] NEW_LINE n = 2 + len ( arr ) NEW_LINE findTwoMissingNumbers ( arr , n ) NEW_LINE