LeetCode 476: Number Complement Solution in Python – A Step-by-Step Guide

What Is LeetCode 476: Number Complement?

In LeetCode 476: Number Complement, you’re given a non-negative integer num, and your task is to find its complement by flipping all its bits in its binary representation—1s to 0s and 0s to 1s—and return the resulting decimal number. For example, num = 5 (binary 101) becomes 2 (binary 010), and num = 1 (binary 1) becomes 0 (binary 0). The problem assumes a 32-bit integer context, but only the significant bits of num matter (no leading zeros beyond its length). It’s like turning a binary light switch upside down to see what glows.

Problem Statement

• Input: num (int)—non-negative integer.
• Output: int—decimal value of num’s binary complement.
• Rules:
• Flip all bits in num’s binary form (1→0, 0→1).
• Return result as decimal.
• Input fits within 32-bit integer.

Constraints

• 0 <= num < 2^31.

Examples to Get Us Started

• Input: num = 5
• Output: 2 (101 → 010).
• Input: num = 1
• Output: 0 (1 → 0).
• Input: num = 7
• Output: 0 (111 → 000).

Understanding the Problem: Flipping the Switch

To solve LeetCode 476: Number Complement in Python, we need to invert the binary representation of num—turning 1s to 0s and 0s to 1s—and compute the resulting decimal value. A naive approach—converting to binary string and flipping—works but could be O(n) with string ops (n = bit length). The key? Use bitwise operations to flip bits directly in O(1) time for 32-bit integers. We’ll explore:

• Best Solution (Bitwise Operations with Mask): O(1) time, O(1) space—fast and optimal.
• Alternative Solution (String Conversion with Flipping): O(n) time, O(n) space—simple but less efficient.

Let’s dive into the bitwise solution—it’s the alchemist’s quick potion we need.

Best Solution: Bitwise Operations with Mask

Why This Is the Best Solution

The bitwise operations with mask approach is the top pick because it’s O(1) time (fixed 32-bit operations) and O(1) space, using XOR and a mask to flip all significant bits of num in a single step. It avoids string conversions, leveraging CPU-level bit manipulation for speed. It’s like flipping a binary switch with a magic wand—elegant and instantaneous!

How It Works

Here’s the strategy:

• Step 1: Flip all bits using XOR (^) with a mask of all 1s:
• num ^ mask flips each bit (0^1=1, 1^1=0).
• Step 2: Create a mask with 1s up to num’s bit length:
• Find highest 1-bit position (e.g., floor(log2(num))).
• Mask = 2^(bit_length) - 1 (e.g., for 5, mask = 111).
• Step 3: Return num ^ mask.
• Why It Works:
• XOR with 1 flips a bit; mask ensures only significant bits flip.
• Bit length calc avoids flipping leading zeros beyond num.

Step-by-Step Example

Example: num = 5

• Binary: 101 (3 bits).
• Bit Length: floor(log2(5)) = 2, mask = 2^3 - 1 = 8 - 1 = 111.
• XOR: 101 ^ 111 = 010 (2 in decimal).
• Result: 2.

Example: num = 1

• Binary: 1 (1 bit).
• Mask: 2^1 - 1 = 1.
• XOR: 1 ^ 1 = 0.
• Result: 0.

Example: num = 7

• Binary: 111 (3 bits).
• Mask: 2^3 - 1 = 7.
• XOR: 111 ^ 111 = 000.
• Result: 0.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

class Solution:
    def findComplement(self, num: int) -> int:
        # Step 1: Find bit length of num
        if num == 0:
            return 1  # Special case: 0 → 1

        # Find highest 1-bit position
        bit_length = 0
        temp = num
        while temp:
            bit_length += 1
            temp >>= 1

        # Step 2: Create mask with all 1s up to bit length
        mask = (1 << bit_length) - 1

        # Step 3: XOR num with mask to flip bits
        return num ^ mask

• Line 4-5: Handle num = 0 (0 → 1).
• Line 8-11: Count bits by shifting until 0 (e.g., 5 → 3 bits).
• Line 14: Mask = 2^bit_length - 1 (e.g., 111 for 5).
• Line 17: XOR flips bits (e.g., 101 ^ 111 = 010).
• Time Complexity: O(1)—32-bit max iterations.
• Space Complexity: O(1)—few variables.

It’s like a bit-flipping spell!

Alternative Solution: String Conversion with Flipping

Why an Alternative Approach?

The string conversion method—O(n) time, O(n) space—converts num to a binary string, flips each bit, and converts back to decimal. It’s slower but intuitive, like writing out the binary on a scroll and inverting it by hand. Good for clarity or learning!

How It Works

• Step 1: Convert num to binary string (e.g., bin(num)[2:]).
• Step 2: Flip each bit (1→0, 0→1).
• Step 3: Convert back to integer.
• Step 4: Return result.

Step-by-Step Example

Example: num = 5

• Binary: "101" (bin(5)[2:]).
• Flip: "010".
• Decimal: int("010", 2) = 2.
• Result: 2.

Code for String Conversion

class Solution:
    def findComplement(self, num: int) -> int:
        # Step 1: Convert to binary string
        binary = bin(num)[2:]  # Remove '0b'

        # Step 2: Flip bits
        flipped = ''.join('1' if bit == '0' else '0' for bit in binary)

        # Step 3: Convert back to integer
        return int(flipped, 2)

• Line 4: Get binary string (e.g., "101").
• Line 7: Flip each bit (e.g., "010").
• Line 10: Convert to decimal (e.g., 2).
• Time Complexity: O(n)—n is bit length (up to 31).
• Space Complexity: O(n)—string storage.

It’s a scroll-flipping scribe!

Comparing the Two Solutions

• Bitwise with Mask (Best):
• Pros: O(1), fast, no strings.
• Cons: Requires bit knowledge.
• String Conversion (Alternative):
• Pros: O(n), intuitive.
• Cons: Slower, more space.

Bitwise wins for efficiency.

Edge Cases and Examples

• Input: num=0 → 1.
• Input: num=2^31-1 → 0 (111...1 → 000...0).
• Input: num=2 → 1 (10 → 01).

Bitwise handles all perfectly.

Complexity Recap

• Bitwise: Time O(1), Space O(1).
• String: Time O(n), Space O(n).

Bitwise’s the champ.

Key Takeaways

• Bitwise: Flip with XOR magic.
• String: Flip by hand.
• Python Tip: Bits beat strings—see [Python Basics](/python/basics).

Final Thoughts: Flip Those Bits

LeetCode 476: Number Complement in Python is a bit-flipping alchemy quest. Bitwise with mask is your fast potion, while string conversion is a slow scroll. Want more bit fun? Try LeetCode 136: Single Number or LeetCode 191: Number of 1 Bits. Ready to invert some numbers? Head to Solve LeetCode 476 on LeetCode and cast it today—your coding skills are bit-ready!