66 ms C++ solution with explanation


  • 0
    F
    1. Counting the number of 1s or 0s in the same position of each bit

    2. The Hamming distance in this bit is (number of 1s * number of 0s)

    3. Total distance is adding the 32-bit-distance together

    Example: [2,14,4]
    0 0 1 0
    1 1 1 0
    0 1 0 0

    counting the number of 1s (or 0s) in each bit: 1,2,2,0 (or 2,1,1,3)
    result = 1x2 + 2x1 + 2x1 + 0x3 = 6

    class Solution {
    public:
        int totalHammingDistance(vector<int>& nums) {
            if(nums.size()<2) return 0;
            int res = 0;
            for(int i = 0; i < 32; ++i)
            {
                int cnt = 0;
                for(int j = 0; j < nums.size(); ++j)
                {
                    cnt += (1 & (nums[j]>>i));
                }
                res += cnt*(nums.size()-cnt);
            }
            return res;
        }
    };
    

Log in to reply
 

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