LeetCode 476: Number Complement

Problem Restatement

We are given a positive integer num.

We need to flip every bit in its binary representation:

Then we return the decimal value of the flipped binary number.

For example, 5 in binary is:

101

After flipping every bit:

010

010 in binary is 2, so the answer is 2.

The problem uses the normal binary representation without leading zeroes. This matters because we only flip the bits that are actually part of num.

Input and Output

Function shape:

def findComplement(num: int) -> int:
    ...

Examples

Example 1:

num = 5

Binary form:

101

Flip every bit:

010

Return:

2

Example 2:

num = 1

Binary form:

1

Flip every bit:

0

Return:

0

First Thought: Convert to String

A simple way is to convert the number to binary text.

For example:

bin(5) == "0b101"

Then we can remove the "0b" prefix, flip each character, and convert the result back to an integer.

class Solution:
    def findComplement(self, num: int) -> int:
        bits = bin(num)[2:]

        flipped = []
        for ch in bits:
            if ch == "0":
                flipped.append("1")
            else:
                flipped.append("0")

        return int("".join(flipped), 2)

This works, and it is easy to understand.

Problem With the String Method

The string method depends on converting between integer and text.

That is fine for this problem, but the problem is really about bits. A direct bit manipulation solution is shorter and closer to the idea.

We want to flip only the meaningful bits of num.

For num = 5, the meaningful bits are:

101

We do not want to think of it as a 32-bit integer like this:

00000000000000000000000000000101

If we directly use ~num, Python gives a negative result because Python integers use signed arithmetic behavior for bitwise complement.

So we need a mask.

Key Insight

To flip exactly the bits of num, build a mask with the same number of bits, all set to 1.

For num = 5:

num  = 101
mask = 111

Now XOR flips every bit where the mask has 1.

101
111
---
010

So:

5 ^ 7 == 2

The mask for a number with k bits is:

(1 << k) - 1

For num = 5, k = 3.

1 << 3 == 8      # binary 1000
8 - 1 == 7       # binary 0111

So the mask is 7, or 111 in binary.

Algorithm

First, find how many bits are needed to represent num.

Python gives this directly:

k = num.bit_length()

Then build the mask:

mask = (1 << k) - 1

Then flip the bits by XOR:

answer = num ^ mask

Return answer.

Correctness

Let k be the number of bits in the binary representation of num.

The mask:

(1 << k) - 1

has exactly k bits, and every one of those bits is 1.

For every bit position used by num, XOR with 1 flips the bit:

Therefore, num ^ mask flips every bit in the binary representation of num.

The mask has no extra 1 bits beyond the length of num, so no leading positions are changed.

Thus the algorithm returns exactly the complement required by the problem.

Complexity

If we write the complexity in terms of the number of bits k, the time is O(k) for computing bit length and bit operations. Under the given constraint, k <= 31, so it is constant.

Implementation

class Solution:
    def findComplement(self, num: int) -> int:
        k = num.bit_length()
        mask = (1 << k) - 1
        return num ^ mask

Code Explanation

This line gets the number of meaningful bits:

k = num.bit_length()

For example:

This line creates a mask of k ones:

mask = (1 << k) - 1

For k = 4:

1 << 4 = 10000
10000 - 1 = 01111

Then this line flips all meaningful bits:

return num ^ mask

For num = 10:

num  = 1010
mask = 1111
xor  = 0101

So the answer is 5.

Testing

def run_tests():
    s = Solution()

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

    print("all tests passed")

run_tests()

Test meaning: