EASY UNDERSTAND o(n) METHOD(java)


  • 0
    M

    hamming distance is the sum of every bit hamming distance
    the bit hamming distance is M*N(M:the number of 1 ,N:the number of 0)

    for instance(consider lowest four bits)
    4,14,2->0100,1110,0010
    the hamming distance of each bit is 1*2+2*1+2*1=6;
    
    public class Solution {
        public int totalHammingDistance(int[] nums) {
            int len=nums.length;
            int ret=0;
            int[] bits=new int[32];
            for(int val:nums){
                int index=0;
                while(val!=0){
                    bits[index++]+=val&1;
                    val=val>>1;
                }
            }
            for(int val:bits){
                ret+=val*(len-val);
            }
            return ret;
        }
    }
    

    or

    public class Solution {
        public int totalHammingDistance(int[] nums) {
            int len=nums.length;
            int ret=0;
            for(int i=0;i<32;i++){
                int Nof1=0;
                for(int val:nums){
                    Nof1+=(val>>i)&1;
                }
                ret+=Nof1*(len-Nof1);
            }
            return ret;
        }
    }
    

Log in to reply
 

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