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
numis 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'
lengthnumber 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
numcan be XOR'ed with its mask in decimal form
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