Leetcode-461. Hamming Distance

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

In this problem, we are tasked with finding the Hamming distance between two integers, `x` and `y`. The Hamming distance is defined as the number of positions where the corresponding bits in the binary representations of the two integers are different. To solve this, we need to compare the binary representation of `x` and `y` bit by bit, and count how many positions differ.

The provided code solves this by using a loop that repeatedly checks the least significant bits of `x` and `y` (obtained via the modulus operation `% 2`). For each pair of bits that are different, the `count` is incremented. This process continues until both `x` and `y` become zero, indicating that all bits have been processed.

Here’s how the code works in detail:

1. The `while(x > 0 || y > 0)` loop continues as long as at least one of the integers still has bits left to process. This ensures that we compare all bits in both integers.

2. Inside the loop, the condition `if (x % 2 != y % 2)` checks if the current least significant bit of `x` is different from the current least significant bit of `y`. If they are different, the `count` is incremented.

3. The values of `x` and `y` are then shifted right by one bit (via integer division by 2), effectively removing the least significant bit from both integers, and the comparison continues with the next bit.

4. Once both integers have been completely processed (i.e., both `x` and `y` become zero), the loop exits, and the final count of differing bits is returned as the Hamming distance.

This approach efficiently computes the Hamming distance by comparing bits directly, and its time complexity is O(log(max(x, y))) because we are processing each bit of the two integers, and the number of bits is logarithmic in the size of the number.

CODE:

class Solution {

public:

    int hammingDistance(int x, int y) {

        int count=0;

        while(x>0||y>0){

          if(x%2!=y%2){

              count++;

              }

            x=x/2;

            y=y/2;

          }

        return count;

    }

};

Also Read

> 3280. Convert Date to Binary

> Leetcode-476 Number complement

> Leetcode-1310. XOR Queries of a Subarray

> Leetcode-3158. Find the XOR of Numbers Which Appear Twice

> 540. Single Element in a Sorted Array

> Leetcode -2220. Minimum Bit Flips to Convert Number