Number Complement

1
2
3

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

Here is a solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def findComplement(self, num: int) -> int:
        """
        Finds the complement of an integer.

        Args:
            num: The integer to find the complement of.

        Returns:
            The complement of the integer.
        """
        # calculate the length of the binary string
        binary_length = len(bin(num)) - 2

        # create a bitmask with 1s where the number has digits
        bitmask = (1 << binary_length) - 1

        # XOR the number with the bitmask to flip its bits
        return num ^ bitmask

This solution works by creating a binary number (bitmask) of the same length as num, but with all bits set to 1. This is achieved by shifting 1 left binary_length times to create a binary number with a 1 followed by binary_length number of 0s, and then subtracting 1 from it to turn all those 0s into 1s.

The complement of num is then found by performing a bitwise XOR operation between num and the bitmask. This works because XOR operation returns 1 if the two bits it’s comparing are different and 0 if they’re the same. Hence, wherever num has a 1, num ^ bitmask will have a 0, and vice versa.

Problem Classification

This problem falls under the category of “Bit Manipulation” problems, as it involves manipulating the binary representation of an integer.

  • What: The problem requires you to calculate the binary complement of a given integer. You need to flip all the 1’s to 0’s and 0’s to 1’s in its binary representation.

  • How: This involves converting the integer into binary, flipping the bits, and then converting back to integer format. But the how is not relevant for this stage of analysis.

The problem can be classified as a “Binary Complement Computation” as it requires some form of computation (bit flipping in this case) to achieve the desired result.

Language Agnostic Coding Drills

Here are the steps to solve this problem:

  1. Binary Conversion: Understand how to convert an integer to its binary form. This is important as the problem is based on the binary representation of an integer.

  2. String Length: Learn how to get the length of a string. This is crucial as you need to know the number of bits in the binary representation.

  3. Power of Two: Understand how to calculate the power of two. This is required to generate a number that has all its binary bits as 1 and same length as the binary representation of the input number.

  4. Bitwise XOR Operation: Understand how to perform a bitwise XOR operation on two integers. This operation is crucial to flipping the bits.

  5. Subtraction Operation: Learn about the subtraction operation which is required to generate the bitmask for flipping the bits.

Approach to solve the problem:

  1. First, convert the integer to binary using the bin() function, which will return a string.

  2. Get the length of the binary representation. Remember to subtract the first two characters returned by bin() function which are ‘0b’ and represent the binary notation in Python.

  3. Calculate the power of two using the length calculated in the previous step and subtract one from the result. This will give a number that has all its binary bits as 1 and is of the same length as the binary representation of the input number.

  4. Finally, perform a bitwise XOR operation between the original integer and the number obtained from the previous step. This will flip all the bits of the original integer and return the complement.

Remember that bitwise XOR operation between a bit and 1 always flips the bit, while a bitwise XOR operation between a bit and 0 leaves it unchanged. That’s why we generate a number that has all its bits as 1 for the XOR operation.

Once all these concepts are understood and coded separately, you can integrate them into the final solution.

Targeted Drills in Python

  1. Binary Conversion: Convert an integer into binary and print the binary representation.

    1
2
3

    num = 5
binary_num = bin(num)
print(binary_num)

    Here, we learn how to convert a number into its binary representation using the bin() function.

  2. String Length: Get the length of a string.

    1
2
3

    str = "101"
len_str = len(str)
print(len_str)

    Here, we learn how to get the length of a string using the len() function.

  3. Power of Two: Calculate the power of two and print the result.

    1
2
3

    pow = 3
power_of_two = 2 ** pow
print(power_of_two)

    Here, we learn how to calculate the power of two using the ** operator.

  4. Bitwise XOR Operation: Perform a bitwise XOR operation between two integers.

    1
2
3
4

    num1 = 5
num2 = 3
result = num1 ^ num2
print(result)

    Here, we learn how to perform a bitwise XOR operation using the ^ operator.

  5. Subtraction Operation: Subtract one number from another and print the result.

    1
2
3
4

    num1 = 8
num2 = 1
result = num1 - num2
print(result)

    Here, we learn how to perform a subtraction operation using the - operator.

Once we understand and implement these concepts separately, we can integrate them into the final solution. The binary conversion and string length operation are used to calculate the number of bits in the binary representation of the number. The power of two calculation and subtraction operations are used to generate the bitmask needed for flipping the bits. The bitwise XOR operation is then used to perform the actual flipping of bits. In the final solution, we integrate all these operations into a single line of code that performs all these operations and returns the final output.