Java O(n) solution and explanation


  • 0

    Use a size 32 array to store the counts of '1' of each binary digit for each number. (Constant space)
    For each digit, the product of count of '0's and '1's is the hamming distance of that digit since if both of 2 numbers have one or zero on the same digit.
    Then, the sum of all the 32 digits is the answer.

    public int totalHammingDistance(int[] nums) {
        int[] digitcounts = new int [32];//count how many ones.
        for(int num:nums){
            for(int i = 0;i<32;i++){
                if(((num>>i)&1)==0){
                    digitcounts[i]++;
                }
            }
        }
        int numbercount = nums.length;
        int sum = 0;
        for(int i = 0;i<32;i++){
            sum+=digitcounts[i]*(numbercount-digitcounts[i]); //count of '1's * count of '0's.
        }
        return sum;
    }

Log in to reply
 

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