LeetCode 1009 - Complement of Base 10 Integer

LeetCode Problem 1009

Difficulty: 🟢 Easy
Topics: Bit Manipulation

Solution

Problem Understanding

This problem asks us to compute the complement of a base-10 integer by flipping every bit in its binary representation. For instance, if the input n is 5, its binary form is 101. Flipping each 0 to 1 and each 1 to 0 produces 010, which equals 2 in decimal. The input is guaranteed to be a non-negative integer less than 10^9. The output should also be a non-negative integer, representing the decimal value of the binary complement.

The problem is straightforward in concept but requires careful handling of binary operations. Edge cases to consider include n = 0, where the binary is 0 and its complement should be 1, and numbers that are all 1s in binary, like 7 (111), whose complement is 0.

Key observations include that we only need to flip bits up to the most significant 1 bit, ignoring leading zeros.

Approaches

The brute-force approach involves converting the number to its binary string, flipping each bit manually, and then converting back to decimal. This works correctly but involves string manipulation and extra space, which is unnecessary for this problem.

The optimal approach relies on bit manipulation. The insight is that to flip all bits of n, we can XOR n with a mask of the same length that has all bits set to 1. For example, for n = 5 (101), the mask is 111 in binary (or 7 in decimal). XORing 5 ^ 7 produces 2, which is the complement.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(log n)	O(log n)	Convert to binary string, flip characters, convert back
Optimal	O(log n)	O(1)	Compute a mask with all 1s up to most significant bit, XOR with n

Algorithm Walkthrough

1. Check if n is zero. If it is, return 1 because the complement of 0 is 1.
2. Initialize a variable mask to 0. This will hold a sequence of 1s the same length as the binary representation of n.
3. Initialize a copy of n in a variable temp.
4. While temp is greater than 0, shift mask left by one and add 1. Simultaneously, shift temp right by one. This builds a mask of all 1s with the same number of bits as n.
5. XOR n with mask. This flips all the bits of n.
6. Return the result of the XOR operation.

Why it works: The XOR operation flips bits where the mask has 1s and leaves bits as 0 unchanged. By constructing a mask that has 1s only in the positions of the original number's bits, we flip exactly the bits that are significant, ignoring leading zeros. This guarantees correctness.

Python Solution

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

The Python solution first handles the special case n = 0. It then constructs the mask by repeatedly left-shifting and adding 1 until all bits in n are accounted for. Finally, it flips the bits using XOR and returns the result.

Go Solution

func bitwiseComplement(n int) int {
    if n == 0 {
        return 1
    }
    
    mask := 0
    temp := n
    for temp > 0 {
        mask = (mask << 1) | 1
        temp >>= 1
    }
    
    return n ^ mask
}

The Go implementation mirrors the Python logic closely. Bitwise operations in Go behave similarly to Python. The only difference is type declarations, but since n is guaranteed to be within int range, there are no overflow concerns.

Worked Examples

Example 1: n = 5

Step	temp	mask	n ^ mask
Initial	5	0	-
Iteration 1	2	1	-
Iteration 2	1	3	-
Iteration 3	0	7	2

Result is 2.

Example 2: n = 7

Step	temp	mask	n ^ mask
Initial	7	0	-
Iteration 1	3	1	-
Iteration 2	1	3	-
Iteration 3	0	7	0

Result is 0.

Example 3: n = 10

Step	temp	mask	n ^ mask
Initial	10	0	-
Iteration 1	5	1	-
Iteration 2	2	3	-
Iteration 3	1	7	-
Iteration 4	0	15	5

Result is 5.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Each loop iteration shifts temp right, which happens log2(n) times
Space	O(1)	Only constant variables mask and temp are used

The complexity is efficient because we only iterate over the number of bits in n, which grows logarithmically with the size of the number.

Test Cases

# Provided examples
assert Solution().bitwiseComplement(5) == 2  # "101" -> "010"
assert Solution().bitwiseComplement(7) == 0  # "111" -> "000"
assert Solution().bitwiseComplement(10) == 5 # "1010" -> "0101"

# Edge cases
assert Solution().bitwiseComplement(0) == 1  # special case
assert Solution().bitwiseComplement(1) == 0  # single-bit number
assert Solution().bitwiseComplement(2) == 1  # "10" -> "01"

# Large numbers
assert Solution().bitwiseComplement(999999999) == 295279706  # test high end of constraint

Test	Why
5	Normal small odd number
7	All ones in binary, result is zero
10	Even number with alternating bits
0	Edge case for zero
1	Single-bit number edge case
2	Smallest multi-bit number
999999999	Large number stress test

Edge Cases

1. n = 0: The binary is a single 0. A naive implementation flipping bits of zero might return zero, but the complement should be 1. Our solution explicitly handles this case.
2. n is a power of two minus one: Numbers like 1, 3, 7, 15 are all ones in binary. Flipping their bits produces 0. This tests that the mask construction correctly accounts for numbers with no zeros in their binary representation.
3. Large numbers: Numbers close to 10^9 test that the solution handles many bits efficiently and does not rely on string conversion or recursion, which could be slow or memory intensive. The bitwise method handles this gracefully.