Total Hamming Distance
Medium · Bit Manipulation · Array · Math · Bit Manipulation
Problem
The Hamming distance of two integers is the number of bit positions where they differ.
Given an integer array nums, return the sum of the Hamming distances over every pair of elements, counting each unordered pair once.
With up to 10^4 numbers there are about 5 · 10^7 pairs, so comparing every pair is too slow. Look at one bit position at a time instead.
Examples
Input: nums = [3,5,6] Output: 6
011, 101 and 110 differ pairwise in two bits each: 2 + 2 + 2 = 6.
Input: nums = [1,1] Output: 0
The only pair is two equal numbers, so nothing differs.
Input: nums = [4,14,2] Output: 6
4 = 0100, 14 = 1110 and 2 = 0010. The pairs 4–14, 4–2 and 14–2 differ in 2 bits each, so the total is 6.
Constraints
- 1 <= len(nums) <= 10^4
- 0 <= nums[i] <= 10^9
- The answer fits in a 32-bit signed integer
Approaches
- Baseline: every pair — time O(n²), space O(1)
Follow-up
The same swap of sums works whenever a pair score adds up over independent positions: the sum of pairwise XORs (weight each bit by 2^b), or the total distance between equal-length strings (count letters per column). It stops working when positions interact, as in the sum of pairwise products of differences.
Related problems
Start free on Cariara · Coding problems · System design studio
