Compute the Total Hamming Distance between All Pairs of Integers

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:
Input: 4, 14, 2

Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note:
Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.

Bruteforce Algorithm to Compute the Hamming distances between Pairs of Integers

We need O(N^2) to iterate over each possible pair of integers, then we can add up the hamming distance with O(logV) complexity. The overall complexity is O(N^2LogV). We can use the std::bitset to perform the counting the set bits.

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++ i) {
            for (int j = i + 1; j < nums.size(); ++ j) {
                int t = nums[i] ^ nums[j];
                ans += bitset<32>(t).count();
            }
        }
        return ans;
    }
};

Alternatively, we can use the compiler intrinsic i.e. __builtin_popcount to achieve the same task.

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++ i) {
            for (int j = i + 1; j < nums.size(); ++ j) {
                int t = nums[i] ^ nums[j];
                ans += __builtin_popcount(t);
            }
        }
        return ans;
    }
};

Iterating the Bits and Perform the Math Counting

As the integers are 32-bit. We can iterate each number, and each bit to count the set bits. Suppose there are n integers, and for a bit, there are k set bits. Thus the overall hamming distances for this bit would have to be k * (n – k). The Hamming distance will be the sum of the XOR bits, thus the combinations between the 1’s and 0’s in the binary representation.

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        if (nums.empty()) return 0;
        int k = nums.size();
        int bits[32];
        std::fill(begin(bits), end(bits), 0);
        for (auto &n: nums) {
            int i = 0;
            while (n > 0) {
                bits[i ++] += n & 0x1;
                n >>= 1;
            }
        }
        int ans = 0;
        for (const auto &n: bits) {
            ans += n * (k - n);
        }
        return ans;
    }
};

The overall complexity is O(N logV). And the space requirement is O(1) constant.

Hamming Weight / Hamming Distance Algorithms

Here are the posts related to Hamming Distance (XOR, The number of different bits):

• A faster approach to count set bits in a 32-bit integer
• Teaching Kids Programming – Minimum Bit Flips to Convert Number (Hamming Distance)
• GoLang: Compute the Hamming Distance
• How to Sort List by Hamming Weight in C++?
• Teaching Kids Programming – Compute the Hamming Distance of Two Integers
• Compute the Total Hamming Distance between All Pairs of Integers
• The Hamming Distance Implementation in Javascript
• Hamming Distance between Two Integers
• Compute Number of 1’s Bits in C/C++
• Teaching Kids Programming – Sort List by Hamming Weight

–EOF (The Ultimate Computing & Technology Blog) —