LeetCode 1009: Complement of Base 10 Integer

Problem Restatement

The complement of an integer is obtained by flipping all its bits.

For example, the decimal number 5 is 101 in binary. Its complement is 010, which is 2.

We are given an integer n and need to return its complement.

Note: the complement does not flip leading zeros (only the bits in the binary representation of n count).

The official constraints state that 0 <= n < 10^9.

Input and Output

Function shape:

def bitwiseComplement(n: int) -> int:
    ...

Examples

Example 1:

n = 5

Binary: 101. Complement: 010 = 2.

Answer:

2

Example 2:

n = 7

Binary: 111. Complement: 000 = 0.

Answer:

0

Example 3:

n = 10

Binary: 1010. Complement: 0101 = 5.

Answer:

5

Key Insight

To flip all bits in the binary representation of n, XOR n with a mask of all 1s of the same bit length.

The mask is 2^bit_length - 1, where bit_length is the number of bits in n.

Special case: n = 0 has no bits to flip, and the complement is 1.

Algorithm

1. If n == 0, return 1.
2. Compute the bit length of n.
3. Create a mask: (1 << bit_length) - 1.
4. Return n XOR mask.

Correctness

XORing with a mask of all 1s flips every bit. The mask has exactly the same number of bits as n, so only the bits in n’s representation are flipped. No leading zeros are introduced.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        if n == 0:
            return 1
        bit_length = n.bit_length()
        mask = (1 << bit_length) - 1
        return n ^ mask

Code Explanation

Handle the zero case:

if n == 0:
    return 1

Compute the number of bits:

bit_length = n.bit_length()

Build the mask of all 1s:

mask = (1 << bit_length) - 1

For example, if n = 5 (101), bit_length = 3, mask = 7 (111).

XOR with the mask flips all bits:

return n ^ mask

5 ^ 7 = 101 ^ 111 = 010 = 2.

Testing

def run_tests():
    s = Solution()

    assert s.bitwiseComplement(5) == 2
    assert s.bitwiseComplement(7) == 0
    assert s.bitwiseComplement(10) == 5
    assert s.bitwiseComplement(0) == 1
    assert s.bitwiseComplement(1) == 0

    print("all tests passed")

run_tests()