Algorithm

Problem Name: 477. Total Hamming Distance

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`.

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 <= 104`
• `0 <= nums[i] <= 109`
• The answer for the given input will fit in a 32-bit integer.

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
int totalHammingDistance(int* nums, int numsSize) {
int i, j, k, t;
t = 0;
for (i = 0; i < 32; i ++) {  // for every bit
k = 0;
for (j = 0; j < numsSize; j ++) {
k += (nums[j] & (1 << i)) ? 1 : 0;  // number of bit 1
}
t += k * (numsSize - k);  // distance on this particular bit
}
return t;
}
``````
Copy The Code &

Input

cmd
nums = [4,14,2]

Output

cmd
6

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int totalHammingDistance(vector& nums) {
int distance = 0;
for(int i = 0; i < 32; i++){
int one = 0, zero = 0;
for(auto x: nums) (x & (1 << i)) ? one++ : zero++;
distance += one * zero;
}
return distance;
}
};
``````
Copy The Code &

Input

cmd
nums = [4,14,2]

Output

cmd
6

#3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int totalHammingDistance(int[] nums) {
int count = 0;
for (int i = 0; i < 32; i++) {
int bitCount = 0;
for (int j = 0; j < nums.length; j++) {
bitCount += (nums[j] >> i) & 1;
}

count += bitCount * (nums.length - bitCount);
}

return count;
}
}
``````
Copy The Code &

Input

cmd
nums = [4,14,4]

Output

cmd
4

#4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const totalHammingDistance = function(nums) {
let total = 0,
n = nums.length;
for (let j = 0; j < 32; j++) {
let bitCount = 0;
for (let i = 0; i < n; i++) bitCount += (nums[i] >> j) & 1;
total += bitCount * (n - bitCount);
}
};

``````
Copy The Code &

Input

cmd
nums = [4,14,4]

Output

cmd
4

#5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def totalHammingDistance(self, nums):
ones, n, res = [0] * 32, len(nums), 0
for num in nums:
for i, c in enumerate(bin(num)[2:][::-1]):
if c == "1": ones[i] += 1
for one in ones: res += one * (n - one)
return res
``````
Copy The Code &

Input

cmd
nums = [4,14,2]

Output

cmd
6