Total Hamming Distance LeetCode Solution

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

Total Hamming Distance LeetCode Solution

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

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;
        }
    }
};Code language: PHP (php)

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;
    }
}Code language: PHP (php)

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;
};Code language: JavaScript (javascript)

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   
Scroll to Top