Domain 1EasyCORE

Number Complement

The problem requires finding the complement of a given positive integer `num`. The complement is obtained by flipping all the bits in its binary representation. For example, if the binary representation of `num` is `101`, its complement would be `010`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Bit Manipulation

476. Number Complement

Model: qwen2.5-coder:14b
Topics: Bit Manipulation
FAANG asked: 1
Acceptance rate: 65.2%


Problem Breakdown

The problem requires finding the complement of a given positive integer num. The complement is obtained by flipping all the bits in its binary representation. For example, if the binary representation of num is 101, its complement would be 010.

Inputs:

  • A positive integer num

Outputs:

  • An integer representing the bit-wise complement of num

Implicit Constraints:

  • The input num fits within a 32-bit signed integer range.
  • There are no leading zero bits in the binary representation of num.

Intuition

A brute-force approach would involve converting the number to its binary form, flipping each bit manually, and then converting it back to an integer. However, this method is inefficient in terms of both time and space complexity.

The key insight is to use bitwise operations to efficiently flip all bits. Specifically, we can XOR num with a mask that has the same number of bits as num, where each bit in the mask is set to 1. This operation will flip all bits in num.

Approach

  1. Determine the Bit Length: Calculate the number of bits required to represent num using log2(num) + 1.
  2. Create a Mask: Generate a mask with all bits set to 1 that has the same length as the bit representation of num. This can be done by shifting 1 left by the bit length and then subtracting 1.
  3. Compute the Complement: Use the XOR operation between num and the mask to flip all bits.

Complexity Analysis

  • Time Complexity: O(log(num)), where log is base 2, due to the calculation of the bit length.
  • Space Complexity: O(1), as we are using a constant amount of extra space.

Solution

def findComplement(num: int) -> int:
    # Determine the number of bits in num
    bit_length = num.bit_length()
    
    # Create a mask with all bits set to 1 that has the same length as num
    mask = (1 << bit_length) - 1
    
    # Compute and return the complement using XOR
    return num ^ mask

Edge Cases Handled

  • Single Bit Number: If num is 1, its binary representation is 1, and the complement should be 0.
  • Power of Two: For numbers like 4 (100 in binary), the complement will be 011 which is 3.
  • Max 32-bit Integer: The solution handles the maximum 32-bit integer by ensuring the mask correctly covers all bits.

This approach ensures that we efficiently compute the bit-wise complement with optimal time and space complexity.