Java Solution with Explanation


  • 13

    The first solution came to my mind is brute forcely iterate through each pair, then sum all Integer.bitCount(x ^ y) like what I mentioned here https://discuss.leetcode.com/topic/72093/java-1-line-solution-d But as you can imagine, it TLE...

    Let's think about this problem another way. We can separate the calculation to do one bit at a time. For example, look at the rightmost bit of all the numbers in nums. Suppose that i numbers have a rightmost 0-bit, and j numbers have a 1-bit. Then out of the pairs, i * j of them will have 1 in the rightmost bit of the XOR. This is because there are i * j ways to choose one number that has a 0-bit and one that has a 1-bit. These bits will therefore contribute i * j towards the total of all the XORs.

    Apply above algorithm to each bit (31 bits in total as specified in the problem), sum them together then we get the answer.

    Reference: http://stackoverflow.com/questions/21388448/sum-of-xor-values-of-all-pairs

    public class Solution {
        public int totalHammingDistance(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;
        }
    }
    

  • 0
    M

    The explanation is very easy to understand! Nice solution!


  • 0

    The explanation is really good. Code could be short.

    public int totalHammingDistance(int[] nums) {
      int n = nums.length;
      int res = 0;
      for(int i = 0; i < 32; i++){
        int c = 0;
        for(int num: nums){
          if(((num >> i) & 1) == 1) c++;
        }
        res += c * (n - c);
      }        
      return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.