Hamming Distance Leetcode Solution

Table of Contents

Problem Statement

In this problem, we are given two integers, A and B, and the goal is to find the hamming distance between the given integers. The integers are greater that/equal to 0 and less than 2³¹

Example

First Integer = 5 , Second Integer = 2

First Integer = 4 , Second Integer = 5

Approach(Counting Bit by Bit)

The first thing which is very clear is that since we need to find the number of bits where the corresponding bit values in the given two numbers are different, we need to do bitwise-XOR of the given integers. The results that XOR will produce in an individual bit position would be ‘1’ if the bits in the two integers at that position were different. Otherwise, the XOR will produce a ‘0’ at that position.

Now that we have deduced this part, the only follow-up remaining is to efficiently find out the numbers of bits which are set (bit value = ‘1’) in the bitwise XOR of the given integers. In order to count this value, we loop for every bit (from 0 to 30) and check whether is set in the XOR value or not.

Algorithm

Store the bitwise XOR of the two integers in a variable – xor_
Initialize cnt = 0 to store the result
For every i = 0 and i < 31:
- If the ‘ith‘ bit is set in xor_
  - Increment cnt: cnt++
- Increment i
Return cnt

Implementation of Hamming Distance Leetcode Solution

C++ Program

#include <bits/stdc++.h>

using namespace std;

int hammingDistance(int x , int y){
    int xor_ = x ^ y , cnt = 0;
    for(int i = 0 ; i < 31 ; i++){
        if((1 << i) & xor_)
            cnt++;
    }
    return cnt;
}

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

Java Program

class hamming_distance{

    static int hammingDistance(int x , int y){
        int xor_ = x ^ y , cnt = 0;
        for(int i = 0 ; i < 31 ; i++){
            if(((1 << i) & xor_) > 0)
                cnt++;
        }
        return cnt;
    }

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

Complexity Analysis of Hamming Distance Leetcode Solution

Time Complexity

O(1) as we perform a constant number of operations regardless of the input.

Space complexity

O(1) as we use constant memory space.

Approach(Counting Bits efficiently – Kernighan’s Algorithm)

The first steps stays the same, which is to find out the bitwise XOR of the teo given numbers. However, we count the number of set bits in their XOR efficiently using the Kernighan’s Algorithm, which is based on the idea:

When we perform ‘bitwise &‘ operation between an integer ‘i’ and ‘i – 1’, its right most set bit is unset.

Let us follow the above idea through an example. Consider N = 36(100100). Now if we ‘&’ it with N – 1, we’d get:

N & (N – 1) = (36 & 35) = (100100 & 100011) = (100000) which clearly unsets the right most bit(at position 2 from the right). Similarly, we can further write:

N & (N – 1) = (32 & 31) = (100000 & 011111) = 000000 which again unsets the rightmost set bit at position 5 from the right. The process can’t be continued further as the integer N has become zero.

This beautiful idea proves to be very useful to count set bits in an integer, as we only need to just iterate as many times as there are set bits in a given integer.

Algorithm

Store the bitwise XOR of the two integers in a variable – xor_
Initialise cnt = 0 to store the result
While xor_ is greater than 0:
1. Increment cnt: cnt++
2. set xor_ = xor_ & (xor_ – 1)
Return cnt

Implementation of Hamming Distance Leetcode Solution

C++ Program

#include <bits/stdc++.h>

using namespace std;

int hammingDistance(int x , int y){
    int xor_ = x ^ y , cnt = 0;
    while(xor_ > 0){
        xor_ = (xor_ & (xor_ - 1));
        ++cnt;
    }
    return cnt;
}

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

Java Program

class hamming_distance{

    static int hammingDistance(int x , int y){
        int xor_ = x ^ y;
        int cnt = 0;
        while(xor_ > 0){
            xor_ = (xor_ & (xor_ - 1));
            ++cnt;
        }
        return cnt;
    }

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