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)
1using System;
2
3public class Solution {
4 public int HammingDistance(int x, int y) {
5 int xor = x ^ y, count = 0;
6 while (xor > 0) {
7 count += xor & 1;
8 xor >>= 1;
9 }
10 return count;
11 }
12
13 public int TotalHammingDistance(int[] nums) {
14 int totalDistance = 0;
15 for (int i = 0; i < nums.Length; i++) {
16 for (int j = i + 1; j < nums.Length; j++) {
17 totalDistance += HammingDistance(nums[i], nums[j]);
18 }
19 }
20 return totalDistance;
21 }
22
23 public static void Main() {
24 int[] nums = {4, 14, 2};
25 Solution sol = new Solution();
26 Console.WriteLine(sol.TotalHammingDistance(nums)); // Output: 6
27 }
28}
29This C# solution mirrors the logic across other languages: using XOR to compute differences for each pair of numbers and iterating over all pairs to find the total Hamming 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)
1function
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.