Hamming Distance
Easy · Bit Manipulation · Bit Manipulation
Problem
The Hamming distance between two integers is the number of bit positions where their binary forms differ: one has a 1 there and the other a 0.
You are given two non-negative integers x and y. Return their Hamming distance.
Examples
Input: x = 5, y = 2 Output: 3
5 is 101 and 2 is 010: all three positions differ.
Input: x = 7, y = 7 Output: 0
Equal numbers have no differing bit.
Input: x = 1, y = 4 Output: 2
1 is 001 and 4 is 100: positions 0 and 2 differ, position 1 matches.
Constraints
- 0 <= x, y <= 2^31 - 1
Approaches
- Compare the bits one position at a time — time O(B), B = 31 bit positions, space O(1)
Follow-up
What if you must add up the Hamming distance over every pair in a list of n numbers? Checking each pair is O(n²). Instead, look at one bit position at a time: if c numbers have a 1 there, that position contributes c · (n − c) differing pairs, which gives O(31 · n) in total.
Related problems
Start free on Cariara · Coding problems · System design studio
