Sponsored
Sponsored
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)
1function hammingDistance(x, y) {
2 let xor = x ^ y, count = 0;
3 while (xor > 0) {
4 count += xor & 1;
5 xor >>= 1;
6 }
7 return count;
8}
9
10function totalHammingDistance(nums) {
11 let totalDistance = 0;
12 for (let i = 0; i < nums.length; i++) {
13 for (let j = i + 1; j < nums.length; j++) {
14 totalDistance += hammingDistance(nums[i], nums[j]);
15 }
16 }
17 return totalDistance;
18}
19
20// Example
21const nums = [4, 14, 2];
22console.log(totalHammingDistance(nums)); // Output: 6
23This JavaScript implementation uses a similar setup: calculating the total Hamming distance of the list by examining the bit differences for each pair through the usage of XOR operation.
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)
1public class Solution {
public int TotalHammingDistance(int[] nums) {
int totalDistance = 0;
for (int i = 0; i < 32; i++) {
int bitCount = 0;
foreach (int num in nums) {
bitCount += (num >> i) & 1;
}
totalDistance += bitCount * (nums.Length - bitCount);
}
return totalDistance;
}
public static void Main() {
int[] nums = {4, 14, 2};
Solution sol = new Solution();
Console.WriteLine(sol.TotalHammingDistance(nums)); // Output: 6
}
}
This C# solution accumulates the total Hamming distance via all bit positions by counting how many numbers have the bit set and using that to calculate the contribution of that particular bit position.