70ms C++ solution O(n)


  • 0
    B

    The idea is to calculate the bitwise summation of all elements in the array, and then determine the sum of hamming distances for all pairs at each bit position.

    For example, the bitwise summation at position i (2^i) is k, and the lens of the array is n, then the sum of all hamming distance for position i would be (n-k)*k. The answer would be the sum of all hamming position sum over 32 positions.

    class Solution {
        void addElement(vector<int> & sum, int a) {
            for (int i = 0; i< 32; i++) {
                sum[i] += a & 1;
                a = a >> 1;
            }
        }
        
    public:
        int totalHammingDistance(vector<int>& nums) {
            int rst = 0, len = nums.size();
            vector<int> sum(32,0);
            
            for (int i : nums) addElement(sum, i);
            
            for (int i = 0; i < 32; i++) {
                //cout << sum[i] << ',';
                rst += sum[i] * (len - sum[i]);
            }
            
            return rst;
        }
    };
    

Log in to reply
 

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