This article includes the code implementation in Python, a detailed explanation, and the complexity analysis for LeetCode - 461. Hamming Distance. Please hit the like button if you find this article is helpful. I will keep writing LeetCode solutions.

Explanation

Since we need to calculate the number of positions at which the corresponding bits are different between two integers x and y. It would be really easy to use exclusive or (XOR) to solve this problem since XOR returns 1 only when the input bits are different. You can check the wiki for more information.

Use example 1 in the problem description.

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

1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

When you do x ^ y which is 1 ^ 4, the return value would be 5 (0 1 0 1).

(^ is the XOR operator in Python)

1   (0 0 0 1)
^
4   (0 1 0 0)
------------
5   (0 1 0 1)

Then we only need to count how many 1 appears in the return value of x ^ y. In this example, there are two 1 appears so the answer is 2.

Code Implementation in Python

    def hammingDistance(self, x: int, y: int) -> int:
        # Use bin() to convert an integer number to a binary string
        xor, differentBit = bin(x ^ y), 0
        for bit in xor:
            if bit == "1":
                differentBit += 1
        return differentBit

Complexity Analysis

# O(n) time | O(1) space - where n is the number of bits to represent x^y