Leetcode – Hamming Distance Solution in Python

Spread the love

Hamming distance is a fundamental concept in information theory and coding theory. It is used extensively in error detection and error correction algorithms. In this article, we will delve into the “Hamming Distance” problem from Leetcode, discuss various approaches to solve it in Python, and analyze their efficiency in terms of time and space complexity.

Table of Contents

  1. Problem Statement and Understanding
  2. Approach 1: Using Bit Manipulation
  3. Approach 2: Using Built-in Functions
  4. Approach 3: Using Brian Kernighan’s Algorithm
  5. Time and Space Complexity Analysis
  6. Conclusion

1. Problem Statement and Understanding

Problem Statement

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance.

Example:

Input: x = 1, y = 4
Output: 2

Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑

The above arrows point to positions where the corresponding bits are different.

Understanding the Problem

The Hamming distance is the count of differing bits between two binary representations. We are given two integers, x and y, and we need to determine the number of bit positions at which they have different values.

2. Approach 1: Using Bit Manipulation

One simple approach is to take the bitwise XOR of x and y. The XOR operation will have bits set where x and y differ. We can then count the number of set bits in the XOR result.

def hammingDistance(x, y):
    # Calculate XOR of x and y
    xor_result = x ^ y
    
    # Count the number of set bits
    hamming_distance = 0
    while xor_result:
        hamming_distance += xor_result & 1
        xor_result >>= 1
    
    return hamming_distance

3. Approach 2: Using Built-in Functions

Python has built-in functions that can help us to solve this problem in a more concise way. We can use the bin function to convert the XOR result into a binary string and then use the count method to count the number of ‘1’s.

def hammingDistance(x, y):
    # Calculate XOR of x and y, convert to binary string and count '1's
    return bin(x ^ y).count('1')

4. Approach 3: Using Brian Kernighan’s Algorithm

Brian Kernighan’s Algorithm is an efficient way to count the number of set bits in a number. The essence of this algorithm is that repeatedly unsetting the rightmost set bit of a number takes k operations, where k is the number of set bits.

def hammingDistance(x, y):
    # Calculate XOR of x and y
    xor_result = x ^ y
    
    # Count the number of set bits using Brian Kernighan’s Algorithm
    hamming_distance = 0
    while xor_result:
        xor_result = xor_result & (xor_result - 1)
        hamming_distance += 1
    
    return hamming_distance

5. Time and Space Complexity Analysis

  • Approach 1: This approach has a time complexity of O(log(max(x, y))) as we iterate through each bit of the XOR result. The space complexity is O(1).
  • Approach 2: This approach also has a time complexity of O(log(max(x, y))) and a space complexity of O(1).
  • Approach 3: The time complexity is O(k) where k is the number of differing bits, which is more efficient in practice. The space complexity is O(1).

6. Conclusion

In this article, we explored different approaches to solving the “Hamming Distance” problem on Leetcode using Python. Understanding bit manipulation techniques and algorithms like Brian Kernighan’s Algorithm is crucial for solving bit manipulation problems efficiently. The Hamming distance is an important concept with diverse applications in coding theory, genomics, cryptography, and more.

Leave a Reply