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.

solution

The simple solution is to calculate the hamming distance for each pair. This is $O(n^2)$.

combinatorics by bit

Instead, we can find how many 0s and 1s occur at each bit index. For each 0, we add one hamming distance to each 1. This can be calculated by numOnes * numZeroes.

class Solution {
	public int totalHammingDistance(int[] nums) {
		int res = 0;
		  
		for (int i=0; i < 32; i++) {
			int ones = 0;
		  
			for (int j=0; j<nums.length; j++) {
				ones += (nums[j] >> i) & 1;
			}
			res += ones * (nums.length-ones);
		}
		  
		return res;
	}
}