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)
1#include <stdio.h>
2int hammingDistance(int x, int y) {
3 int xor = x ^ y, dist = 0;
4 while (xor > 0) {
5 dist += xor & 1;
6 xor >>= 1;
7 }
8 return dist;
9}
10
11int totalHammingDistance(int* nums, int numsSize) {
12 int totalDist = 0;
13 for (int i = 0; i < numsSize - 1; i++) {
14 for (int j = i + 1; j < numsSize; j++) {
15 totalDist += hammingDistance(nums[i], nums[j]);
16 }
17 }
18 return totalDist;
19}
20
21int main() {
22 int nums[] = {4, 14, 2};
23 int result = totalHammingDistance(nums, 3);
24 printf("%d\n", result); // Output: 6
25 return 0;
26}
27This C code defines a function hammingDistance that calculates the Hamming distance between two integers by XORing them and counting the number of 1s in the result. The totalHammingDistance function calculates the sum of Hamming distances for every pair in the array nums.
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)
1function totalHammingDistance
This JavaScript solution calculates the total Hamming distance by summing contributions of different bit positions, capturing how often each bit is set across nums elements.