Scale Engineer

Hamming Distance

Easy
#0448Time: O(k), where k is the number of bits in the larger number. String conversions, padding, and iteration all take time proportional to the number of bits. For 32-bit integers, this is effectively O(1) but with a high constant factor.Space: O(k), where k is the number of bits in the larger number (at most 32). This space is used to store the binary string representations.
Patterns
Bit Manipulation

Prompt

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 <= 231 - 1

 

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

Approaches

5 approaches with complexity analysis and trade-offs.

This approach converts both integers into their binary string representations. It then compares these strings character by character to count the differences. To handle numbers of different bit lengths, the shorter string is padded with leading zeros to match the length of the longer one.

Algorithm

  • Convert x to a binary string using Integer.toBinaryString(x).
  • Convert y to a binary string using Integer.toBinaryString(y).
  • Determine the maximum length of the two strings.
  • Pad the shorter string with leading '0's so both strings have the same length.
  • Iterate from 0 to length - 1.
  • In each iteration, compare the characters at the current index. If they are different, increment a distance counter.
  • Return the final distance.

Walkthrough

This method is straightforward but less performant. It relies on standard library functions to convert numbers to strings and then performs a character-by-character comparison.

  1. Convert both integers x and y to their binary string representations.
  2. Since the binary strings can have different lengths (e.g., Integer.toBinaryString(1) is "1" and Integer.toBinaryString(4) is "100"), we need to make them equal in length by padding the shorter string with leading zeros.
  3. Once they have the same length, we can iterate through them and count the positions where the characters (bits) do not match.
class Solution {    public int hammingDistance(int x, int y) {        String xStr = Integer.toBinaryString(x);        String yStr = Integer.toBinaryString(y);         int lenX = xStr.length();        int lenY = yStr.length();        int maxLen = Math.max(lenX, lenY);         // Pad with leading zeros        while (xStr.length() < maxLen) {            xStr = "0" + xStr;        }        while (yStr.length() < maxLen) {            yStr = "0" + yStr;        }         int distance = 0;        for (int i = 0; i < maxLen; i++) {            if (xStr.charAt(i) != yStr.charAt(i)) {                distance++;            }        }        return distance;    }}

Complexity

Time

O(k), where k is the number of bits in the larger number. String conversions, padding, and iteration all take time proportional to the number of bits. For 32-bit integers, this is effectively O(1) but with a high constant factor.

Space

O(k), where k is the number of bits in the larger number (at most 32). This space is used to store the binary string representations.

Trade-offs

Pros

  • Conceptually simple and easy to understand for those less familiar with bitwise operations.

Cons

  • Inefficient due to the overhead of string creation, manipulation, and memory allocation.

  • Slower than direct bitwise manipulation.

  • Requires extra space to store the string representations.

Solutions

class Solution {public  int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem