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
Example 1:

Input: nums = [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).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Example 2:

Input: nums = [4,14,4]
Output: 4

Constraints:

1 <= nums.length <= 105
0 <= nums[i] <= 109

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    /*
    0100
    1110
    0010
    ----
    2220
      

    */
    public int totalHammingDistance(int[] nums) {
        int count = 0;
        for (int k = 0; k < 32; k++) {
          int zero = 0;
          int nonZero = 0;
          for (int i = 0; i < nums.length; i++) {
               if ((nums[i] & (1 << k)) > 0) {
                    nonZero++;
               } else {
                   zero++;
               }
          }  
          if (nums.length == zero || nums.length == nonZero) continue;    
          // System.out.println("k bit zero " + zero + " nonZero " + nonZero);  
          
          count += nonZero * zero;  
        }
        return count;
    }
}

Solution#

Solution