C++ O(n) solution


  • 0
    V
    class Solution {
    public:
        int totalHammingDistance(vector<int>& nums) {
            vector<int> zeroesBitVec(30, 0);
            vector<int> onesBitVec(30, 0);
            int count = 0;
            if(nums.size() <= 1) return 0;
            initBitVec(zeroesBitVec, onesBitVec, nums[0]);
            for(int i=1; i<nums.size(); i++) {
                int val = nums[i];
                for(int j=0; j<30; j++) {
                    if((val & 1) == 1) {
                        count += zeroesBitVec[j];
                        onesBitVec[j] += 1;
                    } else {
                        count += onesBitVec[j];
                        zeroesBitVec[j] += 1;
                    }
                    if(val > 0) {
                        val >>= 1;
                    }
                }
            }
            return(count);
        }
        
        void initBitVec(vector<int> &zeroesBitVec, vector<int> &onesBitVec, int num) {
            for(int i=0; i<30; i++) {
                if ((num & 1) == 1) {
                    onesBitVec[i] += 1;
                } else {
                    zeroesBitVec[i] += 1;
                }
                if(num > 0) {
                    num >>= 1;
                }
            }
        }
    };
    

Log in to reply
 

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