Coding Interview PatternsTotal Hamming Distance
MediumBitwise Manipulation
Total Hamming Distance
Explanation & Solution
Description
The [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) between two integers is the number of positions at which the corresponding bits are different.
Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.
Input:nums = [4,14,2]
0
4
1
14
2
2
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the last 4 bits). The answer will be:
Hamming(4, 14) + Hamming(4, 2) + Hamming(14, 2) = 2 + 2 + 2 = 6.
Constraints
1 <= nums.length <= 10^40 <= nums[i] <= 10^9
Approach
Bitwise Manipulation pattern
Key Insight
- Instead of O(n²) pairwise comparison, analyze each bit position independently in O(n) — yielding O(32n) = O(n) overall
- Time: O(n) | Space: O(1)
Visualization
Input:
[4, 14, 2]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps