Last updated on January 5th, 2025 at 01:00 am
Here, we see a Total Hamming Distance LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Bit-Manipulation
Companies
Level of Question
Medium
Total Hamming Distance LeetCode Solution
Table of Contents
1. Problem Statement
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
2. Coding Pattern Used in Solution
The coding pattern used in this problem is “Bit Manipulation”. This is because the solution involves analyzing the binary representation of numbers and performing bitwise operations to calculate the Hamming distance.
3. Code Implementation in Different Languages
3.1 Total Hamming Distance C++
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int size = nums.size();
if(size < 2) return 0;
int ans = 0;
int *zeroOne = new int[2];
while(true)
{
int zeroCount = 0;
zeroOne[0] = 0;
zeroOne[1] = 0;
for(int i = 0; i < nums.size(); i++)
{
if(nums[i] == 0) zeroCount++;
zeroOne[nums[i] % 2]++;
nums[i] = nums[i] >> 1;
}
ans += zeroOne[0] * zeroOne[1];
if(zeroCount == nums.size()) return ans;
}
}
};
3.2 Total Hamming Distance Java
class Solution {
public int totalHammingDistance(int[] nums) {
if (nums == null) {
return 0;
}
int distance = 0;
for (int i = 0; i < 32; i++) {
int one_count = 0;
for (int j = 0; j < nums.length; j++) {
one_count += (nums[j] >> i) & 1;
}
distance += one_count * (nums.length - one_count);
}
return distance;
}
}
3.3 Total Hamming Distance JavaScript
var totalHammingDistance = function(nums) {
const cache={};
const toBase2=(n)=>{
const key=n;
if(cache[key]) return cache[key];
const arr=Array(32).fill().map(()=>0);
let pos=0;
while(n>0){
const left=n%2;
arr[pos]=left;
n=Math.trunc(n/2);
pos++;
}
return cache[key]=arr.reverse();
}
let base2mat=[];
for(let i=0;i<nums.length;i++)
base2mat.push(toBase2(nums[i]));
let totalCount=0;
for(let c=0;c<base2mat[0].length;c++){
let zeroes=0, ones=0;
for(let r=0;r<base2mat.length;r++){
zeroes+=base2mat[r][c]===0?1:0;
ones+=base2mat[r][c]===1?1:0;
}
totalCount+=zeroes*ones;
}
return totalCount;
};
3.4 Total Hamming Distance Python
class Solution(object):
def totalHammingDistance(self, nums):
ans = 0
for i in range(32):
zero = one = 0
mask = 1 << i
for num in nums:
if mask & num: one += 1
else: zero += 1
ans += one * zero
return ans
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n * 32) | O(1) |
| Java | O(n * 32) | O(1) |
| JavaScript | O(n * 32) | O(n * 32) |
| Python | O(n * 32) | O(1) |
- Efficiency: The solution avoids the naive O(n^2) approach of comparing all pairs by leveraging bit manipulation to calculate contributions for each bit position.
- Space Usage: The C++, Java, and Python implementations are space-efficient, while the JavaScript implementation uses additional space to store binary representations.
- Bit Manipulation: This approach is highly efficient for problems involving binary representations and bitwise operations.