The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

&nbsp;
Example 1:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.


Example 2:

Input: nums = [4,14,4]
Output: 4


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 104
	0 &lt;= nums[i] &lt;= 109
	The answer for the given input will fit in a 32-bit integer.


class Solution:
    def totalHammingDistance(self, arr: List[int]) -> int:

        total = 0
        for i in range(0,31):
            count = 0
            for j in arr :
                count+= (j >> i) & 1
            total += count*(len(arr)-count)
        return total
class Solution {
    public int totalHammingDistance(int[] nums) {
        int total = 0;
        int[][] cnt = new int[2][32];
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < 32; j++) {
                int idx = (nums[i] >> j) & 1;
                total += cnt[idx ^ 1][j];
                cnt[idx][j]++;
            }
        }
        return total;
    }
}
/*
So in the question we want to find out the 
number of difference of bits between each pair 
so in the brute force we will iterate over the vector 
and for every pair we will calculate the Hamming  distance 
the Hamming distance will be calculated by taking XOR  between the two elements
and then finding out the number of ones in the XOR of those two elements 
the intuition behind this method is that XOR will contain 1's at those places 
where the corresponding bits of  elements x & y are different 
therefore we will add this count
to our answer
*/
class Solution {
public:
    int hammingDistance(int x, int y) {
        int XOR=x^y;
        
        int count=0;
        while(XOR){
            if(XOR&1)
                count++;
            
            XOR=XOR>>1;
        }
        return count;
    }
    
    int totalHammingDistance(vector<int>& nums) {
        int ans=0;
        for(int i=0;i<nums.size()-1;i++){
            for(int j=i+1;j<nums.size();j++){
                ans+=hammingDistance(nums[i],nums[j]);
            }
        }
        
        return ans;
    }
};
var totalHammingDistance = function(nums) {
    let n = nums.length, ans = 0;
    for(let bit = 0; bit < 32; bit++) {
        let zeros = 0, ones = 0;
        for(let i = 0; i < n; i++) {
            ((nums[i] >> bit) & 1) ? ones++ : zeros++;
        }
        ans += zeros * ones;
    }
    return ans;
};
Total Hamming Distance