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)
1#include <iostream>
#include <vector>
int totalHammingDistance(std::vector<int>& nums) {
int totalDistance = 0;
int n = nums.size();
for (int i = 0; i < 32; ++i) {
int bitCount = 0;
for (int num : nums) {
bitCount += (num >> i) & 1;
}
totalDistance += bitCount * (n - bitCount);
}
return totalDistance;
}
int main() {
std::vector<int> nums = {4, 14, 2};
std::cout << totalHammingDistance(nums) << std::endl; // Output: 6
return 0;
}
In this C++ code, each bit position's contribution to the overall Hamming distance is calculated similarly. The variables bitCount and totalDistance are used to tally the contributions.