Last updated on July 18th, 2024 at 03:43 am

Here, We see Total Hamming Distance LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Bit-Manipulation

Companies

Facebook

Level of Question

Medium

Total Hamming Distance LeetCode Solution

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

1. Total Hamming Distance LeetCode Solution 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;
        }
    }
};

2. Total Hamming Distance LeetCode Solution 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. Total Hamming Distance Solution 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;
};

4. Total Hamming Distance Solution 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