[LeetCode] Total Hamming Distance

477. Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int res = 0, freq[32] = {}, count = 0;
for(auto& n : nums) {
for(int i = 0; i < 32; i++) {
int mask = n & (1<<i);
if(mask) {
res += count - freq[i];
freq[i]++;
} else {
res += freq[i];
}
}
count++;
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/06/09/PS/LeetCode/total-hamming-distance/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.