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, return the Hamming distance between them.

Example

Input: x = 1, y = 4
Output: 2
Explanation:
1 (in binary):   0001
4 (in binary):   0100
The Hamming distance is 2 because there are two positions at which the corresponding bits are different.

Clarifying Questions

  1. What is the range of the integers x and y?
    • Typically, this will be within the typical 32-bit signed integer range, but good to confirm.
  2. Do we need to consider negative integers?
    • In most cases for this problem, you can assume non-negative integers.
  3. Do we need to handle edge cases like when x and y are the same?
    • Yes, but the Hamming distance will naturally be 0 in this case.

Strategy

  1. XOR Operation: The XOR operation (^) between two bits results in 1 if the bits are different and 0 if they are the same. Thus, XORing the two numbers will result in a number whose binary representation has 1s in positions where the corresponding bits of the original numbers differ.
  2. Counting the Bits: To find the number of differing bits, we need to count the number of 1s in this resultant number. This can be done using bit manipulation techniques or using built-in functions.

Code

#include <iostream>
using namespace std;

int hammingDistance(int x, int y) {
    int xor_val = x ^ y;
    int distance = 0;
    while (xor_val > 0) {
        if (xor_val & 1) {
            distance++;
        }
        xor_val >>= 1;
    }
    return distance;
}

int main() {
    int x = 1;
    int y = 4;
    cout << "Hamming Distance between " << x << " and " << y << " is " << hammingDistance(x, y) << endl;
    return 0;
}

Explanation

  1. XOR Calculation: The XOR of x and y is computed with int xor_val = x ^ y;.
  2. Bit Counting: Initialize distance to 0. While xor_val is greater than 0, check the least significant bit (LSB) using xor_val & 1. If the LSB is 1, increment the distance. Shift xor_val right by one bit (xor_val >>= 1;) and continue until all bits are checked.

Time Complexity

The space complexity is O(1) as only a few integer variables are used, independent of the input values.

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