The 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.
Example 1:
Input: nums = [4,14,2] Output: 6 Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). The answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Example 2:
Input: nums = [4,14,4] Output: 4
Constraints:
1 <= nums.length <= 1040 <= nums[i] <= 109Problem Overview: Given an integer array nums, compute the sum of Hamming distances for every pair of numbers. The Hamming distance between two integers is the number of bit positions where their binary representations differ.
This problem mixes array iteration with bit manipulation. A direct pairwise comparison works but becomes slow as the array grows. The key observation: Hamming distance is determined independently at each bit position.
Approach 1: Naive Pairwise Calculation (O(n² * B) time, O(1) space)
The straightforward approach checks every pair of numbers in the array. For each pair (i, j), compute the Hamming distance using XOR: x ^ y. The number of set bits in the result tells you how many positions differ. Use a loop or built-in popcount operation to count set bits. Accumulate the distance for all pairs.
This method relies only on simple math and bit operations, making it easy to understand and implement. However, it requires comparing n(n-1)/2 pairs, which quickly becomes expensive for large arrays. With n = 10^4, the quadratic growth makes it impractical. Still useful for verifying correctness or when input sizes are small.
Approach 2: Bit-by-Bit Contribution (O(n * 32) time, O(1) space)
The optimal solution flips the perspective. Instead of examining pairs, analyze each bit position independently. For a given bit index b, count how many numbers have that bit set (ones) and how many do not (zeros). Every pair consisting of one number with bit 1 and one with bit 0 contributes exactly one to the Hamming distance.
The number of such pairs is ones * zeros. Add this value to the total for that bit. Repeat for all 32 bit positions in a standard integer. Each iteration scans the array once and checks the bit using (num >> b) & 1. This converts the quadratic pairwise computation into a linear scan multiplied by the number of bits.
This works because bit positions contribute independently to the Hamming distance. Instead of evaluating every pair, you count how many pairs differ at each position in aggregate. The result is a time complexity of O(n * 32), which simplifies to O(n) for fixed-width integers.
Recommended for interviews: Interviewers expect the bit-by-bit counting approach. The brute-force pairwise method demonstrates understanding of XOR and Hamming distance, but the optimized solution shows you can recognize independent bit contributions and reduce quadratic work to linear time. Most accepted production solutions use the bit counting technique.
This approach involves calculating the Hamming distance for each pair of numbers by comparing their binary representations. This naive method checks each bit position from the least significant bit to the most significant bit for each pair.
This C code defines a function hammingDistance that calculates the Hamming distance between two integers by XORing them and counting the number of 1s in the result. The totalHammingDistance function calculates the sum of Hamming distances for every pair in the array nums.
Time Complexity: O(n^2 * k) where n is the number of numbers and k is the number of bits per integer (32).
Space Complexity: O(1)
For each bit position, count how many numbers have that bit set. The number of pairs from two sets, one having the bit set and the other not, can be computed directly. This reduces the complexity significantly.
This C code iterates through each bit position from 0 to 31. bitCount keeps track of how many numbers have the current bit set. The Hamming distance contribution of this bit is given by bitCount * (numsSize - bitCount).
Time Complexity: O(n * k) where n is the array size and k is 32 (number of bits).
Space Complexity: O(1)
We enumerate each bit in the range [0, 31]. For the current enumerated bit i, we count the number of numbers where the i-th bit is 1, denoted as a. Therefore, the number of numbers where the i-th bit is 0 is b = n - a, where n is the length of the array. In this way, the sum of the Hamming distance on the i-th bit is a times b. We add the Hamming distances of all bits to get the answer.
The time complexity is O(n times log M), where n and M are the length of the array and the maximum value in the array, respectively. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Naive Pairwise Calculation | Time Complexity: O(n^2 * k) where n is the number of numbers and k is the number of bits per integer (32). |
| Bit by Bit Calculation | Time Complexity: O(n * k) where n is the array size and k is 32 (number of bits). |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Pairwise Calculation | O(n² * B) | O(1) | Small arrays or when demonstrating the direct XOR-based Hamming distance calculation |
| Bit-by-Bit Contribution Counting | O(n * 32) ≈ O(n) | O(1) | General case and interview settings where large input sizes require a linear-time solution |
花花酱 LeetCode 477. Total Hamming Distance - 刷题找工作 EP132 • Hua Hua • 3,941 views views
Watch 9 more video solutions →Practice Total Hamming Distance with our built-in code editor and test cases.
Practice on FleetCode