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)
1public class Solution {
2 public int hammingDistance(int x, int y) {
3 int xor = x ^ y, count = 0;
4 while (xor > 0) {
5 count += xor & 1;
6 xor >>= 1;
7 }
8 return count;
9 }
10
11 public int totalHammingDistance(int[] nums) {
12 int totalDistance = 0;
13 for (int i = 0; i < nums.length; i++) {
14 for (int j = i + 1; j < nums.length; j++) {
15 totalDistance += hammingDistance(nums[i], nums[j]);
16 }
17 }
18 return totalDistance;
19 }
20
21 public static void main(String[] args) {
22 Solution sol = new Solution();
23 int[] nums = {4, 14, 2};
24 System.out.println(sol.totalHammingDistance(nums)); // Output: 6
25 }
26}
27This Java implementation consists of the same two functions. The hammingDistance method computes the distance for two integers, and totalHammingDistance iterates through all pairs to compute the total 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#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.