Domain 1EasyCORE

Complement of Base 10 Integer

The problem requires finding the complement of a given non-negative integer `N` in its binary representation. The complement is obtained by flipping all bits in the binary form of `N`. For example: - Input: 5 (binary "101") -> Output: 2 (binary "010") - Input: 7 (binary "111") -> Output: 0 (binary "000") - Input: 10 (binary "1010") -> Output: 5 (binary "0101")

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

1009. Complement of Base 10 Integer

Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 0
Acceptance rate: 61.4%


Problem Breakdown

The problem requires finding the complement of a given non-negative integer N in its binary representation. The complement is obtained by flipping all bits in the binary form of N. For example:

  • Input: 5 (binary “101”) -> Output: 2 (binary “010”)
  • Input: 7 (binary “111”) -> Output: 0 (binary “000”)
  • Input: 10 (binary “1010”) -> Output: 5 (binary “0101”)

Inputs: A non-negative integer N where 0 <= N < 10^9. Outputs: The complement of the binary representation of N, returned as a base-10 integer. Implicit Constraints:

  • No leading zeroes in binary representations except for N = 0.
  • Edge cases include N = 0 and powers of two, which have all bits set to zero except one.

Intuition

A brute-force approach would involve converting the number to a binary string, flipping each bit, and then converting it back to an integer. However, this method is inefficient due to multiple conversions and manipulations of strings.

The key insight is that the complement of N can be found by XORing N with a mask that has all bits set to 1 up to the highest bit in N. This avoids string manipulation and leverages bitwise operations for efficiency.

Approach

  1. Edge Case Handling: If N is 0, return 1 directly since its complement is “1”.
  2. Determine Mask Length: Calculate the number of bits required to represent N in binary.
  3. Create Mask: Generate a mask with all bits set to 1 up to the highest bit position found in step 2.
  4. Compute Complement: XOR N with the mask to get its complement.

Complexity Analysis

  • Time Complexity: O(log N) due to the loop that calculates the number of bits required for N.
  • Space Complexity: O(1) as we are using a constant amount of extra space regardless of input size.

Solution

def bitwiseComplement(N: int) -> int:
    if N == 0:
        return 1
    
    # Determine the number of bits in N
    num_bits = 0
    temp = N
    while temp > 0:
        temp >>= 1
        num_bits += 1
    
    # Create a mask with all bits set to 1 up to num_bits
    mask = (1 << num_bits) - 1
    
    # Compute the complement by XORing N with the mask
    return N ^ mask

Edge Cases Handled

  • N = 0: The code directly returns 1, as the binary representation of 0 is “0”, and its complement is “1”.
  • Powers of Two: For numbers like 2 (binary “10”), 4 (binary “100”), etc., the mask will have all bits set to 1 up to the highest bit position, resulting in a complement that flips only the highest bit.
  • General Case: The approach works for any non-negative integer within the given constraints by flipping all bits in its binary representation.