LeetCode 461: Hamming Distance Solution in Python – A Step-by-Step Guide

What Is LeetCode 461: Hamming Distance?

In LeetCode 461: Hamming Distance, you’re given two integers x and y, and your task is to compute the Hamming distance—the number of positions where their binary representations differ. For example, x = 1 (001) and y = 4 (100) differ in 2 positions: bits 0 and 2 (0-based). It’s like comparing two binary fingerprints to see how many marks don’t match.

Problem Statement

• Input: x (int), y (int)—two integers.
• Output: int—Hamming distance (number of differing bits).
• Rules:
• Count positions where bits differ in binary form.
• Input integers are non-negative.

Constraints

• 0 <= x, y <= 2^31 - 1.

Examples to Get Us Started

• Input: x = 1, y = 4
• Output: 2 (001 vs. 100, differ at positions 0 and 2).
• Input: x = 3, y = 1
• Output: 1 (011 vs. 001, differ at position 1).
• Input: x = 0, y = 0
• Output: 0 (000 vs. 000, no differences).

Understanding the Problem: Counting the Bit Flips

To solve LeetCode 461: Hamming Distance in Python, we need to compare the binary representations of two integers and count positions where their bits differ. A naive approach—converting to binary strings and comparing—works but could be O(n) where n is the bit length. The key? Bitwise operations can do this faster. We’ll explore:

• Best Solution (Bitwise XOR with Bit Counting): O(1) time (32 bits), O(1) space—fast and clever.
• Alternative Solution (String Conversion): O(n) time, O(n) space—simple but less efficient.

Let’s dive into the bitwise solution—it’s the codebreaker’s secret weapon we need.

Best Solution: Bitwise XOR with Bit Counting

Why This Is the Best Solution

The bitwise XOR with bit counting is the top pick because it’s O(1) time (fixed 32-bit integers) and O(1) space, using XOR to identify differing bits and a bit-counting trick to tally them in one go. It’s like flipping a switch to highlight mismatches, then counting the lights—super fast and efficient!

How It Works

Here’s the strategy:

• Step 1: Compute diff = x ^ y (XOR highlights differing bits: 1 where bits differ, 0 where same).
• Step 2: Count 1s in diff:
• Use a loop: shift and check least significant bit (LSB).
• Or use Python’s bin().count('1') (still O(1) for 32 bits).
• Step 3: Return the count.
• Why It Works:
• XOR: 0 ^ 0 = 0, 1 ^ 1 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1.
• Counting 1s in result = number of differing positions.

Step-by-Step Example

Example: x = 1, y = 4

• Binary: x = 001, y = 100.
• XOR: 001 ^ 100 = 101 (diff = 5 in decimal).
• Count 1s:
• 101: LSB = 1 (count=1), shift → 10.
• 10: LSB = 0, shift → 1.
• 1: LSB = 1 (count=2), shift → 0.
• Result: 2.

Example: x = 3, y = 1

• Binary: 011 ^ 001 = 010 (diff = 2).
• Count: 010 has 1 one.
• Result: 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        # Step 1: XOR to find differing bits
        diff = x ^ y

        # Step 2: Count 1s in diff
        count = 0
        while diff:
            count += diff & 1  # Check LSB
            diff >>= 1        # Right shift
        return count

        # Alternative one-liner:
        # return bin(x ^ y).count('1')

• Line 4: XOR x and y (e.g., 1 ^ 4 = 5).
• Line 7-10: Loop:
• diff & 1: Extract LSB (1 if set).
• diff >>= 1: Shift right, process next bit.
• Stop when diff = 0.
• Line 11: Return count.
• Line 13: Alternative using bin() (same complexity).
• Time Complexity: O(1)—32 iterations max for 32-bit int.
• Space Complexity: O(1)—few variables.

It’s like a bit-flipping spotlight!

Alternative Solution: String Conversion with Comparison

Why an Alternative Approach?

The string conversion method turns numbers to binary strings—O(n) time, O(n) space—then compares characters to count differences. It’s slower but intuitive, like laying out two binary tapes and ticking off mismatches. Good for clarity or learning!

How It Works

• Step 1: Convert x and y to binary strings (e.g., bin()).
• Step 2: Pad shorter string with leading zeros.
• Step 3: Compare characters, count differences.
• Step 4: Return count.

Step-by-Step Example

Example: x = 1, y = 4

• Binary: x = "1" (001), y = "100".
• Pad: x = "001", y = "100".
• Compare:
• 0 vs. 1 (diff), 0 vs. 0, 1 vs. 0 (diff).
• Result: 2.

Code for String Conversion

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        # Step 1: Convert to binary strings, remove '0b'
        bin_x = bin(x)[2:]
        bin_y = bin(y)[2:]

        # Step 2: Pad with leading zeros
        max_len = max(len(bin_x), len(bin_y))
        bin_x = bin_x.zfill(max_len)
        bin_y = bin_y.zfill(max_len)

        # Step 3: Count differences
        count = 0
        for i in range(max_len):
            if bin_x[i] != bin_y[i]:
                count += 1

        return count

• Line 4-5: Convert to binary, strip "0b".
• Line 8-9: Pad to equal length (e.g., "001", "100").
• Line 12-15: Compare chars, count diffs.
• Time Complexity: O(n)—n is max bit length (up to 31).
• Space Complexity: O(n)—binary strings.

It’s a tape-comparing tally!

Comparing the Two Solutions

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

Bitwise wins for efficiency.

Edge Cases and More Examples

• Input: x=0, y=0 → 0.
• Input: x=2^31-1, y=0 → 31.
• Input: x=1, y=1 → 0.

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: XOR and count.
• String: Convert and compare.
• Python Tip: Bits beat strings—see [Python Basics](/python/basics).

Final Thoughts: Measure That Distance

LeetCode 461: Hamming Distance in Python is a bit-flipping detective game. The bitwise XOR solution is your fast decoder, while string conversion offers a clear view. Want more bit fun? Try LeetCode 136: Single Number or LeetCode 338: Counting Bits. Ready to count some flips? Head to Solve LeetCode 461 on LeetCode and crack it today—your coding skills are bit-perfect!