# Total Hamming Distance LeetCode Solution

Difficulty Level Medium
Bit ManipulationViews 836

## Problem Statement:

Total Hamming Distance LeetCode Solution:

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

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

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).
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
```

Example 2:

Input:

``` nums = [4,14,4]
```

Output:

``` 4
```

Constraints:

• `1 <= nums.length <= 10`4
• `0 <= nums[i] <= 10`9
• The answer for the given input will fit in a 32-bit integer.

## Approach

### Idea

1. The first solution that comes to our mind is to brute-force iterate through each pair, then sum all `Integer.bitCount(x ^ y)` .So This complexity O(N*N) gives TLE.
2. Now, look into the efficient manner. The total Hamming distance is constructed bit by bit in this approach.
3. For each bit position 1-32 in a 32-bit integer belonging to the array, we count the number of integers in the array which have that bit set.
4. Then, if there are n integers in the array and k of them have a particular bit set and (n-k) do not, then that bit contributes n* (n-k) to the hamming distance.
5. Because for each of the ‘k’ numbers, we have 1 of the (n-k) numbers, that have a different bit and the number of ways to select 1 from k and (n-k) numbers is kC1nkC1=k(nk).
6. For every bit, we will calculate how many are sets and how many are not sets. We will simply multiply both values for every bit position 1-32.
7. To check whether the bit is set or not we can use left shift or right shift bit manipulation.
8.  Look into the below code for a better understanding.

## Code

### Total Hamming Distance LeetCode C++ Solution

```class Solution {
public:
#define ll int
int totalHammingDistance(vector<int>& nums) {
ll i,j,n=nums.size();
ll cnt=0;
for(i=0;i<32;i++)
{
int one=0,zero=0;
for(j=0;j<n;j++)
{
if((nums[j]&(1<<i))>0)
{
one++;
}
else
zero++;
}
cnt+=one*zero;

}
return cnt;
}
};```

### Total Hamming Distance LeetCode Java Solution

```class Solution {
public int totalHammingDistance(int[] nums) {
int i,j,n=nums.length;
int cnt=0;

for(i=0;i<32;i++)
{
int one=0,zero=0;
for(j=0;j<n;j++)
{
if((nums[j]&(1<<i))>0)
{
one++;
}
else
zero++;
}
cnt+=one*zero;

}
return cnt;
}
}
```

## Complexity Analysis for Total Hamming Distance LeetCode Solution

### Time Complexity

Time complexity is O(N*32) or simply say O(N). Where N is the size of the input array.

### Space Complexity

Space complexity is O(1) as we not taking any extra space.

Translate »