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 <iostream>
2#include <vector>
3
4int hammingDistance(int x, int y) {
5 int xorValue = x ^ y, count = 0;
6 while (xorValue) {
7 count += xorValue & 1;
8 xorValue >>= 1;
9 }
10 return count;
11}
12
13int totalHammingDistance(std::vector<int>& nums) {
14 int totalDistance = 0, n = nums.size();
15 for (int i = 0; i < n; ++i) {
16 for (int j = i + 1; j < n; ++j) {
17 totalDistance += hammingDistance(nums[i], nums[j]);
18 }
19 }
20 return totalDistance;
21}
22
23int main() {
24 std::vector<int> nums = {4, 14, 2};
25 std::cout << totalHammingDistance(nums) << std::endl; // Output: 6
26 return 0;
27}
28This C++ code follows the same logic. It uses the hammingDistance function to count differing bits between two integers, and totalHammingDistance 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)
1def
This Python implementation counts the number of set bits at each position over all numbers. It calculates the total Hamming distance by the contribution from each bit position using bit_count * (n - bit_count).