Java Easy solution with explanation


  • 2
    Z

    Hi there! Here the strightforward idea is to calculate haming distances between each pair and then sum them up. But that algorithm runs for O(31 * n^2). We have to make it faster.
    Actually we don't need to consider each pair. Let's simplify the problem, such that each number consists of single bit. How could we solve then? This case we know, that haming distance between two numbers can be either 1 or 0. Well, 1 if bits are different and 0 otherwise. It means, the answer is the number of pairs with different bits. The latter is equals to the product of # of zero bits and # of set bits.
    Our problem is the same. You can prove by yourselves that sum of haming distances is equals to the sum of pairs with different bits for each bit position from 1 to 31. Thus we come up with solution that works for O(1) space and O(31*n) time.

    public class Solution {
        public int totalHammingDistance(int[] nums) {
            int ans= 0 ;
            int bit = 1;
            for(int i = 0;i<31;i++){
                int zero = 0, one = 0;
                for(int j =  0;j<nums.length;j++){
                    if((nums[j]&bit) == 0){
                        zero++;
                    } else {
                        one++;
                    }
                }
                ans+=zero*one;
                bit<<=1;
            }
            return ans;
        }
    }

Log in to reply
 

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