477. Total Hamming Distance

Reference: LeetCode EPI 4.4
Difficulty: Medium

Problem

The 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.

Refer to: 461. Hamming Distance or EPI 4.4

Note:

• Elements of the given array are in the range of 0 to 10^9.
• Length of the array will not exceed 10^4.

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.

Analysis

Methods:

1. Brute-Force (Time Limit Exceeded)

   • Check all the unique pairs of elements for differing bits.
   • xor of two bits 1 if they are not the same, and 0 otherwise.

     public int totalHammingDistance(int[] nums) {
       int n = nums.length;
       int count = 0;
       for (int i = 0; i < n; ++i) {
         for (int j = i + 1; j < n; ++j) {
           count += hammingDistance(nums[i], nums[j]);
         }
       }
       return count;
     }
     
     private int hammingDistance(int x, int y) {
       int xor = x ^ y;
       int count = 0;
       while (xor != 0) {
         xor = xor & (xor - 1);
         count += 1;
       }
       return count;
     }

     Time: $O(N^2 \cdot \log{V}) \sim O(N^2)$ where $V$ is the largest value any of the elements can ever take. Since all elements are less than $10^9$, the value $\log{V}$ is approximately $30$, which is a small constant.
     Space: $O(1)$

2. Combination / Pair

   • For any particular bit position, count the number $k$ of elements with this bit ON / 1. Hence the number of elements with the bit OFF / 0 should be $(n - k)$.
   • For each bit position (32 in total), we have $k$ 1 bits and $(n - k)$ 0 bits, and we want the total number of of combinations (pairs) of 1 and 0, which equals k * (n - k).
   • Note: We can switch the order of loops to reduce space complexity like the code below.

     //      0 1 0 0 -> 4
     //      1 1 1 0 -> 14
     //      0 0 1 0 -> 2
     // -----------------
     // ON:  1 2 2 0
     // OFF: 2 1 1 3
     //      2 2 2 0  <--- # combination = 6
     public int totalHammingDistance(int[] nums) {
       int n = nums.length;
       int sum = 0;
       for (int i = 0; i < 32; ++i) { // outer loop
         int onCount = 0;
         for (int val : nums) {
           val = (val >> i) & 1; // isolate the bit on the lsd position
           onCount += val & 1; // 1&1=1  0&1=0
           // onCount += val ^ 0; // 1^0=1  0^0=0
         }
         sum += onCount * (n - onCount); // combination calculation
       }
       return sum;
     }

     Time: $O(N\log{V}) \sim O(N)$
     Space: $O(\log{V})$ or $O(1)$

3. Vectorized Method

   • Vectorized operations can result in small, elegant, and good performance code. It is supported in Python. The takeaway is that we don’t need the outer loop and instead we process every bit at the same time. For example:

     count = [0 0 0 0];
     for (int val : nums) {
       // val is like [0 1 0 0]
       count += val; // [0 0 0 0] + [0 1 0 0] = [0 1 0 0]
     }
     return sum(count); // sum([2 2 2 0]) = 6