Hamming Distance - Practice Coding Problems

Hamming Distance - Problem

Bit Manipulation Easy

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: For x = 1 (binary: 0001) and y = 4 (binary: 0100), the Hamming distance is 2 because bits differ at positions 0 and 2.

Input & Output

Example 1 — Basic Case

$ Input: x = 1, y = 4

› Output: 2

💡 Note: x = 1 (binary: 0001), y = 4 (binary: 0100). Bits differ at positions 0 and 2, so Hamming distance = 2

Example 2 — Same Numbers

$ Input: x = 3, y = 3

› Output: 0

💡 Note: x = 3 (binary: 11), y = 3 (binary: 11). No bits differ, so Hamming distance = 0

Example 3 — Adjacent Numbers

$ Input: x = 7, y = 8

› Output: 4

💡 Note: x = 7 (binary: 0111), y = 8 (binary: 1000). All 4 bit positions differ, so Hamming distance = 4

Constraints

0 ≤ x, y ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Two integers x and y to compare

Process

XOR the numbers and count set bits

Output

Number of positions with different bits

Key Takeaway

🎯 Key Insight: XOR operation naturally identifies all positions where bits differ, making bit counting the core of the solution

Asked in

f Facebook 15 G Google 12

The key insight is to use XOR operation which gives 1 where bits differ, then count the 1s. Best approach uses Brian Kernighan's algorithm for efficient bit counting. Time: O(k), Space: O(1) where k is number of differing bits.

Common Approaches

Approach	Time	Space	Notes
✓ XOR and Bit Counting	O(log n)	O(1)	Use XOR to find differing bits, then count the 1s
Brute Force - Binary String Comparison	O(log n)	O(log n)	Convert numbers to binary strings and compare each character
Brian Kernighan's Algorithm	O(k)	O(1)	Use Brian Kernighan's bit manipulation trick to count set bits efficiently

XOR and Bit Counting — Algorithm Steps

Compute XOR of x and y
Count the number of 1 bits in the XOR result
Return the count

Visualization

Tap to expand

Step-by-Step Walkthrough

XOR Operation

x XOR y gives 1 where bits differ

Bit Counting

Count number of 1s in XOR result

Result

Total count is Hamming distance

Code -

solution.c — C

#include <stdio.h>

int solution(int x, int y) {
    // XOR to find differing bits
    int xorResult = x ^ y;
    
    // Count the number of 1s in the XOR result
    int count = 0;
    while (xorResult) {
        count += xorResult & 1;
        xorResult >>= 1;
    }
    
    return count;
}

int main() {
    int x, y;
    scanf("%d", &x);
    scanf("%d", &y);
    
    printf("%d\n", solution(x, y));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Counting bits takes O(log n) time where n is the XOR result

⚡ Linearithmic

Space Complexity

O(1)

Only uses a few integer variables

✓ Linear Space

125.0K Views

Medium Frequency

~10 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

XOR and Bit Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler