# Total Hamming Distance LeetCode Solution

Difficulty Level Medium
Bit ManipulationViews 76

## 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 »
{"ft_lang_label":"__label__en","ft_lang_prob":0.71935874,"math_prob":0.99551606,"size":2657,"snap":"2022-40-2023-06","text_gpt3_token_len":758,"char_repetition_ratio":0.11911044,"word_repetition_ratio":0.06696428,"special_character_ratio":0.3007151,"punctuation_ratio":0.14359862,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99986076,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-01-27T07:12:58Z\",\"WARC-Record-ID\":\"<urn:uuid:80a18998-c2ff-49a1-9e30-ca02ff4e981b>\",\"Content-Length\":\"175679\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:22b03187-e7ff-446b-bd41-3962c952c8e8>\",\"WARC-Concurrent-To\":\"<urn:uuid:1b50eac3-2f1b-449d-84f1-8eb5178c7287>\",\"WARC-IP-Address\":\"50.16.49.81\",\"WARC-Target-URI\":\"https://www.tutorialcup.com/leetcode-solutions/total-hamming-distance-leetcode-solution.htm\",\"WARC-Payload-Digest\":\"sha1:SJVUYVEZ7Y6VPDE65NUROVTYTUZ4UN2Z\",\"WARC-Block-Digest\":\"sha1:32NXRPITYKGHWOG7C4HEQFIPLVQ2GXPZ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-06/CC-MAIN-2023-06_segments_1674764494974.98_warc_CC-MAIN-20230127065356-20230127095356-00739.warc.gz\"}"}