Leetcode – Number Complement Solution in Python

The Number Complement problem is an interesting algorithmic challenge often encountered on Leetcode. This article delves into the Number Complement problem, discussing different strategies to solve it efficiently in Python.

Problem Statement:

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Example:

Input: 5
Output: 2
Explanation: The binary representation of 5 is 101, and its complement is 010, which is 2 in decimal.

Understanding the Problem:

Before we dive into solving this problem, it is crucial to understand what bit manipulation is and how the complement of a number can be calculated. In binary representation, the complement of a bit is achieved by flipping it; 0 becomes 1, and 1 becomes 0.

Approach 1: Bit by Bit Complementation

One approach to solve this problem is to iterate through each bit of the given number, flip it, and calculate the complement number.

def findComplement(num):
    binary = bin(num)[2:]  # Convert to binary and remove the '0b' prefix
    complement = ''
    
    # Flip each bit
    for bit in binary:
        complement += '1' if bit == '0' else '0'
    
    # Convert back to integer
    return int(complement, 2)

This approach is straightforward, but it involves string manipulation, which is not the most efficient way to handle bits.

Approach 2: Bit Manipulation with XOR

We can solve this problem more efficiently using bitwise operators. One operator that can be particularly useful here is XOR (^). The XOR operation between two bits results in 1 if the bits are different, and 0 if they are the same. This property can be exploited to flip bits by XORing them with 1.

def findComplement(num):
    i = 1
    while i <= num:
        num ^= i
        i <<= 1
    return num

This approach is based on the observation that XORing a bit with 1 flips it. The variable i takes values that are powers of 2 (1, 2, 4, 8, …) and is used to flip the respective bits of the number.

Approach 3: Using Bit Mask

Another elegant approach is to use a bit mask. The idea is to create a mask that has all bits set to 1 up to the position of the highest bit set in the original number. By XORing this mask with the original number, we effectively flip all the relevant bits.

def findComplement(num):
    # Find the highest bit set
    highest_bit = len(bin(num)) - 2
    
    # Create the mask with all bits set to 1
    mask = (1 << highest_bit) - 1
    
    # XOR the number with the mask
    return num ^ mask

This approach is efficient and involves minimal bit manipulation.

Generalization: Handling Negative Numbers

The problem statement specifies positive integers, but we can generalize the solution to handle negative integers as well. For negative integers, we need to consider the two’s complement representation.

def findComplement(num):
    if num < 0:
        # Convert to two's complement and remove the '-0b' prefix
        binary = bin(num & 0xFFFFFFFF)[3:]
    else:
        binary = bin(num)[2:]
    
    complement = ''
    
    # Flip each bit
    for bit in binary:
        complement += '1' if bit == '0' else '0'
    
    # Convert back to integer
    return int(complement, 2)

Conclusion:

The Number Complement problem is an excellent exercise for understanding bit manipulation and binary representations. We have explored various approaches to solve this problem in Python – ranging from basic bit-by-bit complementation to more advanced techniques using bit manipulation with XOR and bit masks. While the problem initially seems simple, efficiently solving it and generalizing it to handle different cases can be challenging and educative. Such problems are not only critical for coding interviews but also for building a strong foundation in algorithms and bit manipulation.