LeetCode 476 - Number Complement

Difficulty: 🟢 Easy
Topics: Bit Manipulation

Solution

Problem Understanding

The problem asks us to compute the complement of a positive integer by flipping every bit in its binary representation. A binary complement means changing every 1 bit into 0, and every 0 bit into 1.

For example, the integer 5 is represented in binary as 101. Flipping each bit gives 010, which is equal to 2 in decimal form.

A very important detail in this problem is that we only flip the bits that are part of the number's actual binary representation. We do not consider leading zeroes. For example, the binary representation of 5 is 101, not 00000101. If we included leading zeroes, the answer would become ambiguous because integers are stored with different fixed widths on different systems.

The input is a single integer num, and we must return another integer representing the flipped binary value.

The constraints are:

1 <= num < 2^31

These constraints tell us several important things:

The number is always positive, so we never need to handle negative integers.
The maximum size is small enough that any bit manipulation approach will run extremely fast.
Since the number fits within 31 bits, integer overflow is not a concern in Python, and it is also safe in Go using standard integer operations.

An important edge case is when num = 1. Its binary representation is simply 1, and flipping it produces 0. Another subtle point is making sure we only flip the meaningful bits and not extra leading bits introduced by machine representation.

Approaches

Brute Force Approach

A brute force solution would convert the number into a binary string, iterate through every character, flip each bit manually, then convert the resulting binary string back into an integer.

For example:

5 becomes "101"
Flip each character:
'1' -> '0'
'0' -> '1'
'1' -> '0'
Result becomes "010"
Convert back to decimal, yielding 2

This works because binary strings directly expose the bits we need to modify. However, this approach involves repeated string operations and conversions between integer and string formats.

Although the constraints are small enough that this would still pass, it is not the most elegant or efficient solution because the problem is fundamentally about bit manipulation.

Optimal Bit Manipulation Approach

The key insight is that XOR can flip bits efficiently.

If we create a bitmask consisting entirely of 1s with the same length as the binary representation of num, then XORing the number with that mask flips every bit.

For example:

num = 5
Binary representation: 101
Mask with same number of bits: 111
XOR operation:
101 ^ 111 = 010

Result: 2

The main challenge is constructing the correct mask.

We can build the mask dynamically by repeatedly shifting left and adding 1 until the mask contains enough bits to cover the number.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k)	O(k)	Converts to binary string and flips characters manually
Optimal	O(k)	O(1)	Uses bitmask and XOR for direct bit manipulation

Here, k represents the number of bits in the binary representation of num.

Algorithm Walkthrough

Optimal Algorithm

Initialize a variable called mask to 1.

The purpose of the mask is to eventually become a sequence of all 1s that matches the length of the binary representation of num. 2. Continue expanding the mask while it is smaller than num.

At each step:

Shift the mask left by one bit.
Add 1.

This process gradually creates masks like:

1
11
111
1111

Once the mask is large enough, perform XOR between num and mask.

XOR has the property:

1 ^ 1 = 0
0 ^ 1 = 1

Therefore, XOR with a mask of all 1s flips every bit. 4. Return the XOR result.

Why it works

The algorithm works because the mask contains exactly the same number of significant bits as num, and every bit in the mask is 1. XORing any bit with 1 flips it. Since we only include the meaningful bits of num, the result is precisely the complement defined by the problem.

Python Solution

class Solution:
    def findComplement(self, num: int) -> int:
        mask = 1
        
        while mask < num:
            mask = (mask << 1) | 1
        
        return num ^ mask

The implementation starts by creating a mask initialized to 1.

The while loop keeps extending the mask by shifting it left and setting the new least significant bit to 1. This gradually builds a sequence of consecutive 1s.

For example:

1
11
111
1111

Once the mask is large enough to cover all bits in num, the XOR operation flips every bit in the number.

The final return statement produces the complement directly using bit manipulation, avoiding any string conversion.

Go Solution

func findComplement(num int) int {
    mask := 1

    for mask < num {
        mask = (mask << 1) | 1
    }

    return num ^ mask
}

The Go implementation follows the exact same logic as the Python version.

One small language difference is the use of := for variable declaration and initialization. Go integers are fixed-width types, but the problem constraints guarantee that all operations remain safely within range.

No additional handling for overflow or special integer behavior is necessary.

Worked Examples

Example 1

Input:

num = 5

Binary representation:

Step-by-step execution

Step	mask (binary)	mask (decimal)	Condition
Initial	1	1	1 < 5
Iteration 1	11	3	3 < 5
Iteration 2	111	7	7 >= 5

Now compute XOR:

Value	Binary
num	101
mask	111
XOR result	010

Result:

Example 2

Input:

num = 1

Binary representation:

Step-by-step execution

Step	mask (binary)	mask (decimal)	Condition
Initial	1	1	1 is not less than 1

Now compute XOR:

Value	Binary
num	1
mask	1
XOR result	0

Result:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k)	The loop runs once for each bit in the number
Space	O(1)	Only a few integer variables are used

The algorithm scales with the number of bits required to represent the input integer. Since integers are at most 31 bits long, the runtime is effectively constant in practice. The memory usage remains constant because no additional data structures are allocated.

Test Cases

sol = Solution()

assert sol.findComplement(5) == 2       # Basic example: 101 -> 010
assert sol.findComplement(1) == 0       # Smallest valid input
assert sol.findComplement(2) == 1       # 10 -> 01
assert sol.findComplement(7) == 0       # 111 -> 000
assert sol.findComplement(8) == 7       # 1000 -> 0111
assert sol.findComplement(10) == 5      # 1010 -> 0101
assert sol.findComplement(15) == 0      # All bits are 1
assert sol.findComplement(16) == 15     # Power of two
assert sol.findComplement(31) == 0      # Another all-ones number
assert sol.findComplement(50) == 13     # 110010 -> 001101
assert sol.findComplement(100) == 27    # Larger input
assert sol.findComplement(1023) == 0    # Ten consecutive 1 bits

Test Summary

Test	Why
`num = 5`	Validates the primary example
`num = 1`	Tests smallest allowed input
`num = 2`	Tests simple two-bit number
`num = 7`	Tests all bits already set to `1`
`num = 8`	Tests power of two behavior
`num = 10`	Tests alternating bit pattern
`num = 15`	Tests another all-ones value
`num = 16`	Tests larger power of two
`num = 31`	Tests five consecutive `1`s
`num = 50`	Tests mixed bit arrangement
`num = 100`	Tests larger arbitrary input
`num = 1023`	Tests many consecutive bits

Edge Cases

One important edge case is when the input is 1. Its binary representation contains only a single bit. A careless implementation might accidentally produce a negative number or include extra leading bits. In this solution, the mask remains 1, and 1 ^ 1 correctly produces 0.

Another important case occurs when the number is a power of two, such as 8 (1000 in binary). These numbers contain a single 1 followed by zeroes. The algorithm correctly constructs a mask of 1111, and XOR produces 0111, which equals 7.

A third subtle edge case is when all bits are already 1, such as 7 (111) or 31 (11111). Flipping every bit should produce 0. The mask construction guarantees the XOR operation flips every significant bit exactly once, so the result becomes all zeroes.

A final consideration is avoiding leading zeroes. Machine integers are typically stored using fixed widths such as 32 or 64 bits. If we simply used the bitwise NOT operator directly, we could accidentally flip unwanted leading bits and produce negative numbers. Constructing a mask that matches only the significant bits ensures the implementation behaves exactly as the problem defines.