Hamming Distance

Companies:
  • Amazon Interview Questions

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.

Note:
0 ≤ xy < 231.

Sample Test Cases

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.

Problem Solution

1)We find XOR of x and y , Why?
Because the xor makes the bit to set if the bits bits are different ie, 1^0 or 0^1 gives the result 1,
Now if we count number of bits which are set int result of XOR gives the hamming distance.

2)How to find if some ith bit is set?
To find if ith bit a number N is set
(i) (N & (1<<i)) >0
(ii) ((N>>i) & 1) ==1
any of the above can be used to check the status of ith bit.
If we find that if any bit is set we increase count.
Hence we start with 0th bit and shift right 1 bit each time and check the status of each bit.

Complexity Analysis

Time Complexity: O(1) since we always need to iterate from 0 to 31 (int).

Space Complexity: O(1) does not require any data structure to store anything.

Code Implementation

#include <bits/stdc++.h>
using namespace std;

 int hammingDistance(int x, int y) {
        int xr = x^y;
        int hd = 0,setBit=1;
        for (int i = 0;i<31;i++)
        {
            if ((xr & setBit)> 0)
                hd++;

            setBit <<= 1;
        }
        return hd;

    }

int main()
{

    cout <<hammingDistance(3,4)<< endl;

    return 0;
}

 

Scroll to Top