TotalHammingDistance477.java

/**
 * The Hamming distance (https://en.wikipedia.org/wiki/Hamming_distance) between
 * two integers is the number of positions at which the corresponding bits are different.
 *
 * Now your job is to find the total Hamming distance between all pairs of the given numbers.
 *
 * Example:
 * Input: 4, 14, 2
 *
 * Output: 6
 *
 * Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is
 * 0010 (just showing the four bits relevant in this case). So the answer will
 * be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2)
 * = 2 + 2 + 2 = 6.
 *
 * Note:
 * Elements of the given array are in the range of 0 to 10^9
 * Length of the array will not exceed 10^4.
 */


public class TotalHammingDistance477 {
 /**
 * https://discuss.leetcode.com/topic/72092/java-o-n-time-o-1-space
 */
 public int totalHammingDistance2(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;
 }


 /**
 * https://discuss.leetcode.com/topic/72104/java-solution-with-explanation
 */
 public int totalHammingDistance2(int[] nums) {
 int n = 31;
 int len = nums.length;
 int[] countOfOnes = new int[n];
 for (int i = 0; i < len; i++) {
 for (int j = 0; j < n; j++) {
 countOfOnes[j] += (nums[i] >> j) & 1;
 }
 }
 int sum = 0;
 for (int count: countOfOnes) {
 sum += count * (len - count);
 }
 return sum;
 }

}