Number Complement - Leetcode Solution

The Number Complement problem on LeetCode asks us to find the complement of a given positive integer. The complement of a number is the bitwise inversion of the number. In other words, we need to flip all the bits (0 to 1 and 1 to 0) in the binary representation of the integer to get its complement.

For example, if the given integer is 5 (represented in binary as 101), the complement will be (010), which is 2 in decimal notation.

The following is a detailed solution to the Number Complement problem on LeetCode using bitwise operators:

1. Convert the given integer to its binary representation: We can convert the given integer to its binary representation using the built-in bin() function in Python. The bin() function returns a binary string prefixed with 0b. We need to remove the 0b prefix to get the binary string representation of the integer.

   Example:

   n = 5
   binary_n = bin(n)[2:]
   print(binary_n) # Output: 101
   

2. Create a mask to flip all the bits: We need to create a mask to flip all the bits in the binary representation of the integer. We can do this by creating a binary number with all 1s of the same length as the binary representation of the integer.

   Example:

   mask = int('1'*len(binary_n), 2)
   print(mask) # Output: 7 (which is 111 in binary)
   

3. Find the bitwise complement: We can find the bitwise complement of the binary representation of the integer by performing a bitwise XOR between the binary representation of the integer and the mask we created.

   Example:

   complement = int(binary_n, 2) ^ mask
   print(complement) # Output: 2
   

4. Return the complement: Finally, we need to return the complement as an integer.

   Example:

   return complement
   

The overall code for the solution to the Number Complement problem on LeetCode would look like this:

class Solution:
    def findComplement(self, num: int) -> int:
        # step 1
        binary_n = bin(num)[2:]

        # step 2
        mask = int('1'*len(binary_n), 2)

        # step 3
        complement = int(binary_n, 2) ^ mask

        # step 4
        return complement

The time complexity of this algorithm is O(log n) as the number of iterations required depends on the number of bits in the given integer.

1