Total Hamming Distance
https://leetcode.com/problems/total-hamming-distance/description/
O(n)
public int totalHammingDistance(int[] nums) {
int total = 0, n = nums.length;
for (int j=0;j<32;j++) {
int bitCount = 0;
for (int i=0;i<n;i++)
bitCount += (nums[i] >> j) & 1;
total += bitCount*(n - bitCount);
}
return total;
}
O(n^2) time limit error
class Solution {
public int totalHammingDistance(int[] nums) {
int res = 0;
for(int i = 0; i < nums.length - 1; i++){
for(int j = i + 1; j < nums.length; j++){
res += compareTwoBits(nums[i], nums[j]);
}
}
return res;
}
private int compareTwoBits(int n1, int n2){
int num = 0;
for(int i = 0; i < 32; i++){
num += ((n1 >> i) & 1) == ((n2 >> i) & 1)? 0 : 1;
}
return num;
}
}