Total Hamming Distance Solutions in C++

// Source : https://leetcode.com/problems/total-hamming-distance/
// Author : Calinescu Valentin
// Date   : 2017-01-09



/*
*  Solution 1 - O(N)
*
* The total Hamming Distance is equal to the sum of all individual Hamming Distances
* between every 2 numbers. However, given that this depends on the individual bits of
* each number, we can see that we only need to compute the number of 1s and 0s for each
* bit position. For example, we look at the least significant bit. Given that we need to
* calculate the Hamming Distance for each pair of 2 numbers, we see that the answer is
* equal to the number of 1s at this position * the number of 0s(which is the total number
* of numbers - the number of 1s), because for each 1 we need to have a 0 to form a pair.
* Thus, the solution is the sum of all these distances at every position.
*/
class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        long long solution = 0;
        int ones[31];
        for(int i = 0; i < 31; i++)
            ones[i] = 0;
        for(vector<int>::iterator it = nums.begin(); it != nums.end(); ++it)
        {
            for(int i = 0; (1 << i) <= *it; i++) //i is the position of the bit
                if((1 << i) & *it)//to see if the bit at i-position is a 1
                    ones[i]++;
        }
        for(int i = 0; i < 31; i++)
            solution += ones[i] * (nums.size() - ones[i]);
        return solution;
    }
};

/// Source : https://leetcode.com/problems/total-hamming-distance/
/// Author : liuyubobobo
/// Time   : 2020-05-25

#include <iostream>
#include <vector>

using namespace std;


/// Count one and zero for every bits position
/// Time Complexity: O(nlog(num))
/// Space Complexity: O(1)
class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {

        vector<vector<int>> cnt(32, vector<int>(2, 0));
        for(int e: nums){
            int i = 0;
            while(e) cnt[i ++][e % 2] ++, e /= 2;
            while(i < 32) cnt[i ++][0] ++;
        }

        int res = 0;
        for(int i = 0; i < 32; i ++) res += cnt[i][0] * cnt[i][1];
        return res;
    }
};


int main() {

    vector<int> nums1 = {4, 14, 2};
    cout << Solution().totalHammingDistance(nums1) << endl;
    // 6

    vector<int> nums2 = {1337};
    cout << Solution().totalHammingDistance(nums2) << endl;
    // 0

    return 0;
}

/// Source : https://leetcode.com/problems/total-hamming-distance/
/// Author : liuyubobobo
/// Time   : 2020-05-25

#include <iostream>
#include <vector>

using namespace std;


/// Count one for every bits position
/// Time Complexity: O(nlog(num))
/// Space Complexity: O(1)
class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {

        vector<int> cnt(32, 0);
        for(int e: nums){
            int i = 0;
            while(e) {
                if(e % 2) cnt[i] ++;
                i ++, e /= 2;
            }
        }

        int res = 0;
        for(int i = 0; i < 32; i ++) res += cnt[i] * (nums.size() - cnt[i]);
        return res;
    }
};


int main() {

    vector<int> nums1 = {4, 14, 2};
    cout << Solution().totalHammingDistance(nums1) << endl;
    // 6

    vector<int> nums2 = {1337};
    cout << Solution().totalHammingDistance(nums2) << endl;
    // 0

    return 0;
}