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)
1def hammingDistance(x, y):
2 xor = x ^ y
3 return bin(xor).count('1')
4
5def totalHammingDistance(nums):
6 total_distance = 0
7 n = len(nums)
8 for i in range(n):
9 for j in range(i + 1, n):
10 total_distance += hammingDistance(nums[i], nums[j])
11 return total_distance
12
13# Example usage
14nums = [4, 14, 2]
15print(totalHammingDistance(nums)) # Output: 6
16In Python, the hammingDistance function computes the XOR of two numbers and uses the bin().count('1') method to count 1s in the binary representation. The totalHammingDistance function calculates the sum of Hamming distances between all pairs.
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.