Java O(n) time, O(1) space. Damn easy.


  • 1
    Z

    Think of this way: it's trivial if you know how many zero and one bits are there in the array for each ith bit (i from 0 to 31).
    Count zeros and ones for each ith digits, and multiply them.

    
    public class Solution {
        public int totalHammingDistance(int[] ns) {
            int sum = 0;
            
            for(int i =0; i < 32; i ++){
                int ones = 0;
                for(int v: ns){
                    ones += ((v >> i) & 0x01)  ; // add 1 or 0;
                }
                int zeros = (ns.length - ones);
                sum +=  zeros * ones;
            }
                
            return sum;
        }
    }
    
    

Log in to reply
 

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