Java Solution with Explanation


  • 18

    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!


  • 3

    The explanation is really good. Code could be short.

    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] & 1;
              nums[j] = nums[j] >> 1;
            }
            res += ones * (nums.length - ones); // ones * zeros
          }
          return res;
        }
    }

  • 0
    D
    This post is deleted!

  • 0
    S

    @Jerry Thanks for you solution! Putting the 32 bit at the outer loop could save us some space.

    I'm a newbie, and I want to check the complexity of this solution with you:

    Time: should be O(n). Although we seem to have two for-loops here, the outer one can only operate a fixed 32 times, so it can be viewed as constant.

    Space: should be O(1), since we don't allocate extra space for arrays and stuff.

    Is my analysis correct? Thank you so much!


Log in to reply
 

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