algoadvance

Leetcode 461. Hamming Distance

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.

Clarifying Questions

  1. Input Range: What are the constraints on the values of x and y?
    • Answer: Both x and y are integers, 0 ≤ x, y < 2^31.
  2. Output: What should the output be?
    • Answer: An integer representing the Hamming distance between x and y.

Strategy

  1. XOR Operation: Use the XOR (^) operation on x and y. This will give a number that has bits set to 1 wherever the bits of x and y are different.
  2. Count Set Bits: Count the number of 1s in the binary representation of the result from the XOR operation. This can be done using various methods in Java, the most efficient and simple being Integer.bitCount().

Code

Here’s how you can implement this:

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

    public static void main(String[] args) {
        HammingDistance hd = new HammingDistance();
        
        // Example usage:
        System.out.println(hd.hammingDistance(1, 4));  // Output: 2
    }
}

Explanation

  1. XOR Operation x ^ y:
    • For two bits a and b, a ^ b is 1 if a is different from b, else it is 0.
    • Example:
      • x = 1 (binary 0001)
      • y = 4 (binary 0100)
      • x ^ y gives 0101 (binary) which is 5.
  2. Counting 1s:
    • Integer.bitCount(5) counts the number of 1s in the binary representation of 5 (binary 0101). There are two 1s.
    • Hence, the Hamming distance is 2.

Time Complexity

Thus, the overall time complexity is O(1).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI