Easy to understand Python solution O(1)


  • 2
    P

    If you want to find the complement of a number (say 5, i.e. 101 in binary), you can simply XOR it with a mask of one's like so: 101 XOR 111 = 010, which is equal to 2 in decimal. Length of the mask would equal length of binary representation of given number. Finding this length would take O(log N) time, where N is the number itself.

    But this can be done using Python functions like so:

    • Find the binary representation: binary_num = bin(num), which gives the string of the form '0b101' for the number 5.
    • The length of binary representation of the given number num is equal to length of the above string minus 2 because we omit the two leftmost characters (i.e. '0' and 'b'): length = len(binary_num) - 2
    • A string mask can then be generated by multiplying the string '1' length number of times: mask = '1'*length
    • This binary string can be converted to integer using int(string, 2) function, where first argument is the string to be converted to integer and second argument is the base in which we need the integer: mask_int = int(mask, 2) In this case, we need binary, so base = 2.
    • Finally, the given number num can be XOR'ed with its mask in decimal form mask_int like so: result = num ^ mask_int, which is the number we need to return.

    All the above steps can be done in a simple one liner:

    class Solution:
        def findComplement(self, num):
            return int('1'*(len(bin(num))-2), 2) ^ num
    

  • 0
    P

    Thank you for kind explanation. :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.