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). 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
Constraints:
1 <= nums.length <= 1040 <= 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;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int totalHammingDistance(vector<int>& 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;
}
};
Input
Output
#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;
}
}
Input
Output
#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);
}
return total;
};
Input
Output
#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
Input
Output