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] <= 109The key idea in #477 Total Hamming Distance is to compute the sum of Hamming distances for every pair of numbers in the array. A naive approach would compare every pair and count differing bits, but this leads to O(n^2) comparisons, which becomes inefficient for large inputs.
A more efficient strategy uses bit manipulation. Instead of comparing pairs directly, analyze each bit position (0–31 for standard integers). For a given bit position, count how many numbers have that bit set (1) and how many do not (0). Every pair consisting of one 1 and one 0 contributes exactly one to the Hamming distance. Therefore, the contribution for that bit is count_ones * count_zeros.
By repeating this calculation for all bit positions and summing the results, you obtain the total Hamming distance. This reduces the time complexity to O(n * B), where B is the number of bits (typically 32). The algorithm only uses a few counters, resulting in O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force Pair Comparison | O(n^2 * B) | O(1) |
| Bit Counting (Optimal) | O(n * B) | O(1) |
Knowledge Center
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.
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)
1using System;
2
3public class Solution {
4 public int HammingDistance(int x, int y) {
5 int xor = x ^ y, count = 0;
6 while (xor > 0) {
7 count += xor & 1;
8 xor >>= 1;
9 }
10 return count;
11 }
12
13 public int TotalHammingDistance(int[] nums) {
14 int totalDistance = 0;
15 for (int i = 0; i < nums.Length; i++) {
16 for (int j = i + 1; j < nums.Length; j++) {
17 totalDistance += HammingDistance(nums[i], nums[j]);
18 }
19 }
20 return totalDistance;
21 }
22
23 public static void Main() {
24 int[] nums = {4, 14, 2};
25 Solution sol = new Solution();
26 Console.WriteLine(sol.TotalHammingDistance(nums)); // Output: 6
27 }
28}
29This C# solution mirrors the logic across other languages: using XOR to compute differences for each pair of numbers and iterating over all pairs to find the total Hamming distance.
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.
Time Complexity: O(n * k) where n is the array size and k is 32 (number of bits).
Space Complexity: O(1)
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of Hamming distance and bit manipulation problems are commonly discussed in technical interviews at FAANG and similar companies. This problem tests understanding of bitwise operations, optimization, and recognizing patterns that reduce pairwise comparisons.
Each differing bit between two numbers contributes exactly one to their Hamming distance. By counting how many numbers have 1s and 0s at a specific bit, you can determine how many pairs differ at that position. This avoids checking every pair individually.
The optimal approach uses bit manipulation by evaluating each bit position across all numbers. For every bit, count how many numbers have a 1 and how many have a 0, then multiply these counts to get the contribution. Summing this for all bits yields the total Hamming distance efficiently.
The optimal solution typically uses simple counters and bit operations rather than complex data structures. Arrays or variables track the number of set bits at each position, keeping the implementation lightweight and efficient.
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).