java o(n), iterative solution with explanation


  • 0
    M

    At each bit position, count the number of 0's and the number of 1's, multiply those to get the contribution of this bit position. Sum those for all bit positions.
    On other words, look at the rightmost bit of all the numbers in the array. Suppose that a numbers have a rightmost 0-bit, and b numbers have a 1-bit. Then out of the pairs, ab* of them will have 1 in the rightmost bit. This is because there are ab* ways to choose one number that has a 0-bit and one that has a 1-bit.

    Hope it is helpful.

    public class Solution {
        public int totalHammingDistance(int[] nums) {
            
            if(nums.length==0)
                return 0;
            
        	
        	int len=nums.length;
        	
        	int[] countofones = new int[32];
        	
        	for(int num:nums){
        		for(int j=0; j<countofones.length; j++){
        			countofones[j] +=(num>>j)&1; 
        		}
        	}
        	
        	int sum=0;
        	
        	for(int count :countofones){
        		sum+=count*(len-count);
        	}
        	
        	return sum;
        
            
        }
    }
    

Log in to reply
 

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