461. Hamming Distance - Solution & Explanation

Q: Is Hamming Distance easy or hard?

Hamming Distance is classified as an Easy problem. The main insight is recognizing that XOR reveals differing bit positions. Once that idea is clear, counting set bits completes the solution in a few lines of code.

Q: Hamming Distance Python/Java solution

In Python, compute x ^ y and count set bits using bin(x ^ y).count('1') or bit operations. In Java, use Integer.bitCount(x ^ y). Both approaches run in constant time with O(1) space and rely on built-in bit counting utilities.

Q: How to solve Hamming Distance in O(1)?

Compute x ^ y to identify the differing bit positions, then count the number of 1s in the result. Because integer size is fixed, the bit counting step runs in constant time. Many languages also provide built-in functions like popcount to compute the result efficiently.

Q: What is the best approach for Hamming Distance?

The optimal approach uses XOR followed by counting the number of set bits. XOR highlights exactly the positions where two integers differ, turning the problem into a population count task. This solution runs in O(1) time because integers have a fixed bit width and uses O(1) extra space.

Q: Is Hamming Distance asked at Google/Amazon/Meta?

Hamming Distance appears frequently in coding interviews at companies that test bit manipulation fundamentals. Variants or related questions have been reported in interviews at companies such as Amazon, Google, and Meta because they test understanding of XOR and bit counting techniques.

Q: What data structure is used in Hamming Distance?

No specialized data structure is required. The solution relies on bitwise operations such as XOR, AND, and bit shifting. These operations are part of standard integer manipulation and fall under the bit manipulation category.

Q: What is the time complexity of Hamming Distance?

Using the XOR approach, the time complexity is O(1) because at most 32 or 64 bits are processed depending on the integer type. If Brian Kernighan’s algorithm is used, the runtime becomes O(k), where k is the number of differing bits. Space complexity remains O(1).

The problem

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, return the Hamming distance between them.

Example 1:

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.

Example 2:

Input: x = 3, y = 1
Output: 1

Constraints:

0 <= x, y <= 2³¹ - 1

Note: This question is the same as 2220: Minimum Bit Flips to Convert Number.

Approach overview

Problem Overview: Hamming Distance measures how many bit positions differ between two integers. Given two numbers x and y, return the number of positions where their binary representations contain different bits.

Approach 1: XOR + Bit Counting (O(1) time, O(1) space)

The key observation is that the XOR operation highlights differing bits. When you compute x ^ y, every bit position where x and y differ becomes 1, and matching positions become 0. The task then reduces to counting how many 1 bits exist in the XOR result. You can iterate through the bits using bit shifts and check the least significant bit with num & 1, or use built‑in population count functions available in most languages. Since integers have a fixed bit width (usually 32 or 64 bits), the runtime is effectively constant.

This approach directly applies bit manipulation techniques. It is simple, efficient, and the most commonly expected answer during interviews. The algorithm performs one XOR operation followed by a small loop over the bits, making it both readable and optimal.

Approach 2: XOR + Brian Kernighan’s Bit Trick (O(k) time, O(1) space)

Instead of checking every bit, you can repeatedly remove the lowest set bit using the expression n = n & (n - 1). Each iteration clears one 1 from the XOR result. Count how many times this operation runs until the number becomes zero. The loop executes exactly once for each set bit, so the runtime is O(k), where k is the number of differing bits.

This technique is a classic optimization in bit manipulation and relies on properties of bitwise operations. It avoids scanning all 32 bits and becomes faster when the XOR result contains only a few set bits.

Recommended for interviews: Start with the XOR insight. Interviewers expect you to recognize that differing bits correspond to 1s in x ^ y. A straightforward bit count already achieves optimal constant time. Mentioning Brian Kernighan’s trick shows deeper familiarity with bit manipulation patterns and often earns extra points. Both approaches use O(1) space and operate within the fixed integer bit width.

Approach 1: Using XOR and Bit Manipulation

To calculate the Hamming distance between two numbers, the most efficient way is to use the XOR operation. The result of XOR operation between two numbers highlights the bits that are different. Once you have the XOR result, the task reduces to counting the number of 1s in the binary representation of this number, which indicates the number of differing bits, thus giving the Hamming distance.

Python

def hammingDistance(x, y):
    return bin(x ^ y).count('1')

x = 1
y = 4
print(hammingDistance(x, y))

Java

public class HammingDistance {
    public static int hammingDistance(int x, int y) {
        int xor = x ^ y;
        int count = 0;
        while (xor != 0) {
            count += xor & 1;
            xor >>= 1;
        }
        return count;
    }

    public static void main(String[] args) {
        int x = 1, y = 4;
        System.out.println(hammingDistance(x, y));
    }
}

C++

#include <iostream>
using namespace std;

int hammingDistance(int x, int y) {
    int xor = x ^ y;
    int count = 0;
    while(xor != 0) {
        count += xor & 1;
        xor >>= 1;
    }
    return count;
}

int main() {
    int x = 1, y = 4;
    cout << hammingDistance(x, y) << endl;
    return 0;
}

JavaScript

function hammingDistance(x, y) {
    let xor = x ^ y;
    let count = 0;
    while (xor !== 0) {
        count += xor & 1;
        xor >>= 1;
    }
    return count;
}

console.log(hammingDistance(1, 4));

#include <stdio.h>

int hammingDistance(int x, int y) {
    int xor = x ^ y;
    int count = 0;
    while(xor != 0) {
        count += xor & 1;
        xor >>= 1;
    }
    return count;
}

int main() {
    int x = 1, y = 4;
    printf("%d\n", hammingDistance(x, y));
    return 0;
}

using System;

class HammingDistance {
    public static int Calculate(int x, int y) {
        int xor = x ^ y;
        int count = 0;
        while (xor != 0) {
            count += xor & 1;
            xor >>= 1;
        }
        return count;
    }

    static void Main() {
        int x = 1, y = 4;
        Console.WriteLine(Calculate(x, y));
    }
}

We use Python's bin() to convert the XOR result to a binary string and count('1') to count differing bits easily.

Complexity

Time Complexity: O(1) since integer size is constant.
Space Complexity: O(1) as space usage is constant.

Try this approach in the editor

Approach 2: Default Approach

TypeScript

function hammingDistance(x: number, y: number): number {
    x ^= y;
    let ans = 0;
    while (x) {
        x -= x & -x;
        ++ans;
    }
    return ans;
}

func hammingDistance(x int, y int) int {
	return bits.OnesCount(uint(x ^ y))
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using XOR and Bit Manipulation	Time Complexity: O(1) since integer size is constant. Space Complexity: O(1) as space usage is constant.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
XOR + Bit Counting	O(1)	O(1)	General case. Simple and readable solution using XOR and counting set bits.
XOR + Brian Kernighan’s Algorithm	O(k)	O(1)	When the XOR result has few set bits. Efficient bit trick that removes one set bit per iteration.

Frequently asked questions

Is Hamming Distance easy or hard?

Hamming Distance is classified as an Easy problem. The main insight is recognizing that XOR reveals differing bit positions. Once that idea is clear, counting set bits completes the solution in a few lines of code.

Hamming Distance Python/Java solution

In Python, compute x ^ y and count set bits using bin(x ^ y).count('1') or bit operations. In Java, use Integer.bitCount(x ^ y). Both approaches run in constant time with O(1) space and rely on built-in bit counting utilities.

How to solve Hamming Distance in O(1)?

Compute x ^ y to identify the differing bit positions, then count the number of 1s in the result. Because integer size is fixed, the bit counting step runs in constant time. Many languages also provide built-in functions like popcount to compute the result efficiently.

What is the best approach for Hamming Distance?

The optimal approach uses XOR followed by counting the number of set bits. XOR highlights exactly the positions where two integers differ, turning the problem into a population count task. This solution runs in O(1) time because integers have a fixed bit width and uses O(1) extra space.

Is Hamming Distance asked at Google/Amazon/Meta?

Hamming Distance appears frequently in coding interviews at companies that test bit manipulation fundamentals. Variants or related questions have been reported in interviews at companies such as Amazon, Google, and Meta because they test understanding of XOR and bit counting techniques.

What data structure is used in Hamming Distance?

No specialized data structure is required. The solution relies on bitwise operations such as XOR, AND, and bit shifting. These operations are part of standard integer manipulation and fall under the bit manipulation category.

What is the time complexity of Hamming Distance?

Using the XOR approach, the time complexity is O(1) because at most 32 or 64 bits are processed depending on the integer type. If Brian Kernighan’s algorithm is used, the runtime becomes O(k), where k is the number of differing bits. Space complexity remains O(1).

Hamming Distance solution and explanation

The problem

Approach overview

Approach 1: Using XOR and Bit Manipulation

Approach 2: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Hamming Distance solution and explanation

The problem

Approach overview

Approach 1: Using XOR and Bit Manipulation

Approach 2: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems