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.

1
2
3
4
5
6
7
8
9
10
11
12
13

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;
    }
};

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.

1
2
3
4
5
6
7
8
9
10
11
12
13

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;
    }
};

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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;
    }
};

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.

–EOF (The Ultimate Computing & Technology Blog) —