Total Hamming Distance
Medium · Bit Manipulation · Explanation and code example
Count Different Bits Independently
How it works
At a fixed bit position, every pair with one set bit and one clear bit contributes one to Hamming distance. If ones values have that bit set, its contribution is ones × (n - ones). Sum this over the 30 relevant bit positions.
Steps
- For each bit, count set bits among the input values.
- Multiply that count by the number of clear bits.
- Sum all bit contributions.
Complexity
- Time: O(30n), or O(n) for the stated integer bound.
- Space: O(1).
Things to watch for
- Do not divide the product by two; set/clear groups already count each pair once.
- The 30-bit bound comes from the input constraints.
- Equal values contribute zero.
Python code example
class Solution:
def totalHammingDistance(self, nums: list[int]) -> int:
MAX_BIT = 30
ans = 0
for i in range(MAX_BIT):
ones = sum(num & (1 << i) > 0 for num in nums)
zeros = len(nums) - ones
ans += ones * zeros
return ans
C++ code example
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
constexpr int maxMask = 1 << 30;
int ans = 0;
for (int mask = 1; mask < maxMask; mask <<= 1) {
const int ones =
ranges::count_if(nums, [mask](int num) { return num & mask; });
const int zeros = nums.size() - ones;
ans += ones * zeros;
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.