LeetCode-477 Total Hamming Distance

Description

给定数组\(a[]\)，求数组内任意元素对的汉明距离之和

Constraints

• \(1 \le a.length \le 10^4\)
• \(0 \le a_i \le 10^9\)
• 返回值必然在整型int范围内

Solution

按位处理贡献，每一位统计0和1的贡献

Code

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int res = 0;
        for(int i = 31; ~i; --i) {
            int bucket = 0;
            for(auto n : nums) {
                bucket += n >> i & 1;
            }
            res += bucket * (nums.size() - bucket);
        }
        return res;
    }
};

Link

LeetCode-477 Total Hamming Distance