Total Hamming Distance
MedPrompt
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] <= 109- The answer for the given input will fit in a 32-bit integer.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly follows the problem definition. It iterates through every possible pair of numbers in the input array, calculates the Hamming distance for each pair, and sums them up to get the total.
Algorithm
- Initialize a variable
totalDistanceto 0. - Get the length of the array,
n. - Use a nested loop to iterate through all unique pairs of indices
(i, j)where0 <= i < j < n. - For each pair of numbers
(nums[i], nums[j]):- Calculate their bitwise XOR:
xorResult = nums[i] ^ nums[j]. - Count the number of set bits (1s) in
xorResult. This can be done efficiently using a built-in function likeInteger.bitCount(). - Add this count to
totalDistance.
- Calculate their bitwise XOR:
- After iterating through all pairs, return
totalDistance.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. It involves generating all possible unique pairs of numbers from the input array and calculating the Hamming distance for each one.
To do this, we can use a nested loop. The outer loop runs from i = 0 to n-1 and the inner loop from j = i + 1 to n-1, where n is the length of the array. This ensures that we consider each pair exactly once.
For each pair (nums[i], nums[j]), we calculate their Hamming distance. A clever way to do this is to use the bitwise XOR operator (^). The result of nums[i] ^ nums[j] is an integer where a bit is set to 1 if and only if the corresponding bits in nums[i] and nums[j] were different. Therefore, the number of set bits in the XOR result is equal to the Hamming distance. Most languages provide a built-in function to count set bits (e.g., Integer.bitCount() in Java), which simplifies this step.
We maintain a running sum, and for each pair, we add their calculated Hamming distance to this sum. After the loops complete, this sum is the total Hamming distance for all pairs.
class Solution { public int totalHammingDistance(int[] nums) { int n = nums.length; if (n < 2) { return 0; } int totalDistance = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Calculate the XOR of the two numbers int xorResult = nums[i] ^ nums[j]; // The number of set bits in the XOR result is the Hamming distance totalDistance += Integer.bitCount(xorResult); } } return totalDistance; }}Complexity
Time
O(N^2). We have two nested loops to iterate through all N * (N-1) / 2 pairs. For each pair, calculating the Hamming distance takes constant time (as integers have a fixed number of bits, e.g., 32). Thus, the overall complexity is quadratic.
Space
O(1). The algorithm uses a fixed amount of extra space for variables like `totalDistance` and loop counters, regardless of the input size.
Trade-offs
Pros
It is simple to understand and implement.
The logic directly maps to the problem's definition.
It uses constant extra space.
Cons
The time complexity is O(N^2), which is too slow for the given constraints (N up to 10^4).
This approach will likely result in a 'Time Limit Exceeded' (TLE) error on most online judges.
Instead of comparing pairs of numbers, this more efficient approach considers the problem from a bit-level perspective. It calculates the total Hamming distance by summing up the contributions of each individual bit position (from 0 to 31) across all numbers.
Algorithm
- Initialize
totalDistanceto 0 andnto the length of thenumsarray. - Iterate through each bit position
ifrom 0 to 30 (since numbers are less than 2^31). - For each bit position
i:- Initialize a counter
countOnesto 0. - Iterate through each number
numin thenumsarray. - Check if the
i-th bit ofnumis set. This can be done using the expression((num >> i) & 1) == 1. - If the bit is set, increment
countOnes. - After counting, calculate the number of elements with a '0' at this bit position:
countZeros = n - countOnes. - The contribution of this bit to the total distance is the number of pairs with different bits, which is
countOnes * countZeros. - Add this product to
totalDistance.
- Initialize a counter
- After iterating through all bit positions, return
totalDistance.
Walkthrough
A more optimal approach is to change the perspective. Instead of summing the distances pair by pair, we can sum the contributions of each bit position to the total distance. The total Hamming distance is the sum of distances at each bit position.
For any single bit position (say, the i-th bit), its contribution to the total Hamming distance is the number of pairs of numbers in the array that have different values at this bit. If we can calculate this for each bit and sum them up, we get the final answer.
Let's focus on one bit position, i. We can iterate through all the numbers in nums and count how many of them have a '1' at this position. Let this count be k. Since there are n numbers in total, it means n - k numbers must have a '0' at this position.
To form a pair with different bits at position i, we must choose one number from the group of k numbers (with a '1') and one number from the group of n - k numbers (with a '0'). The total number of such pairs is k * (n - k). Each of these pairs contributes exactly 1 to the total Hamming distance at this specific bit position.
By repeating this process for all 31 relevant bit positions (for numbers up to 10^9) and summing up the results (k * (n - k) for each bit), we arrive at the total Hamming distance for all pairs.
class Solution { public int totalHammingDistance(int[] nums) { int totalDistance = 0; int n = nums.length; // Iterate through each bit position from 0 to 30 // (since 10^9 < 2^30, we only need to check up to bit 30). for (int i = 0; i < 31; i++) { int countOnes = 0; // For the current bit i, count how many numbers have it set for (int num : nums) { if (((num >> i) & 1) == 1) { countOnes++; } } // The number of numbers with a 0 at bit i is n - countOnes int countZeros = n - countOnes; // The contribution from this bit is the number of pairs with different bits totalDistance += countOnes * countZeros; } return totalDistance; }}Complexity
Time
O(N * K), where N is the number of elements in the array and K is the number of bits in the integer type (e.g., 32). Since K is a constant, the complexity is effectively linear, O(N). This is a significant improvement over the O(N^2) brute-force approach.
Space
O(1). We only use a few variables for the total sum, counts, and loop indices, which does not depend on the size of the input array.
Trade-offs
Pros
Highly efficient with a linear time complexity, O(N).
Easily passes the time limits for the given constraints.
Maintains a constant space complexity.
Cons
The logic is less direct than the brute-force approach and requires thinking about the problem from a bit-level perspective.
Solutions
Solution
class Solution {public int totalHammingDistance(int[] nums) { int ans = 0; for (int i = 0; i < 31; ++i) { int a = 0, b = 0; for (int v : nums) { int t = (v >> i) & 1; a += t; b += t ^ 1; } ans += a * b; } return ans; }}class Solution: def totalHammingDistance(self, nums: List[int]) -> int: ans = 0 for i in range(31): a = b = 0 for v in nums: t = (v >> i) & 1 if t: a += 1 else: b += 1 ans += a * b return ansclass Solution {public: int totalHammingDistance(vector<int> &nums) { int ans = 0; for (int i = 0; i < 31; ++i) { int a = 0, b = 0; for (int &v : nums) { int t = (v >> i) & 1; a += t; b += t ^ 1; } ans += a * b; } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.