Compute the Total Hamming Distance between All Pairs of Integers

  • 时间:2020-09-18 17:01:02
  • 分类:网络文摘
  • 阅读:87 次

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) —

推荐阅读:
谁来保障转基因食品的公众知情权?  适宜老年人的秋令养阴滋补的菜肴  营养专家建议的老年人健康饮食原则  绑架“第一口奶”该曝光的不仅是多美滋  汇源等多家国产果汁巨头卷入“烂果门”  两性营养保健:哪些食物让男人更持久  地沟油勾兑成调和油 检测仍无成熟技术  中医食疗:用蜂蜜治咳嗽,标本兼治!  常吃辛辣烫的食物易患消化道肿瘤  老年人可适当吃些零食保证营养需求 
评论列表
添加评论