algoadvance

1009. Complement of Base 10 Integer

Every non-negative integer n has a binary representation. For example, 5 can be represented as “101” in binary, and its complement is “010” which is the number 2.

Given an integer n, return its complement. The complement strategy is to flip the bits of its binary representation.

Example 1:

Example 2:

Constraints:

Strategy

To solve the problem, the strategy involves the following steps:

  1. Convert to Binary: Use the built-in bin() function to get the binary representation of the integer.
  2. Flip Bits: Generate a mask that has the same length of bits as the binary representation of n with all bits set to 1.
  3. Apply the Mask: XOR the number with the mask to flip its bits.
  4. Return Result: Convert the result back to a decimal integer and return it.

Code Implementation

Here’s the Python code to achieve the solution:

def bitwiseComplement(n: int) -> int:
    if n == 0:
        return 1
    
    # Calculate the bit length of n
    bit_length = n.bit_length()
    
    # Create a mask of the same bit length with all 1s
    mask = (1 << bit_length) - 1
    
    # XOR n with the mask to get the complement
    return n ^ mask

Clarifying Questions

  1. Edge Cases: Confirm if the edge cases like n = 0 are handled (since the bitwise complement of 0 should be 1).
  2. Constraints: Make sure the input range [0, 10^9] is respected, and the function is expected to handle large numbers efficiently.

Time Complexity

The time complexity of this solution is O(1) because:

  1. The bit length of an integer can be calculated in O(1) time.
  2. Creating the mask and applying the XOR operation are both O(1) operations.

Thus, the provided solution is efficient and works within the given constraints.

Try our interview co-pilot at AlgoAdvance.com