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