Total Hamming Distance - Leetcode Solution

The Total Hamming Distance problem on LeetCode is a popular problem that can be solved using various approaches, including brute-force and bit manipulation. Here we will discuss a couple of solutions to this problem.

The problem statement is as follows: Given an array of n integers nums, calculate the total Hamming distance between all pairs of the integers in the array.

Solution 1: Brute-Force Approach

A naive approach to solve this problem is to calculate the Hamming distance between each pair of integers in the array and sum them up. This approach has a time complexity of O(n^2) and will fail for large input arrays.

Here's the implementation of the brute-force approach:

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int n = nums.size();
        int totalHammingDist = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                totalHammingDist += hammingDistance(nums[i], nums[j]);
            }
        }
        return totalHammingDist;
    }
    
private:
    int hammingDistance(int x, int y) {
        int diffBits = 0;
        while (x || y) {
            diffBits += (x & 1) ^ (y & 1);
            x >>= 1;
            y >>= 1;
        }
        return diffBits;
    }
};

In the above implementation, we have used a nested loop to iterate over each pair of integers in the array. The hammingDistance function is used to calculate the Hamming distance between two integers. It takes two integers as input and returns the number of different bits between them.

This implementation works well for small input arrays but will not perform well for larger ones as the time complexity is O(n^2).

Solution 2: Bit Manipulation

To optimize the above solution, we can use bit manipulation. The idea is to calculate the total Hamming distance bit by bit. We can count the number of 1's and 0's in each bit position for all the integers in the array. Then, for each bit position, we can calculate the number of pairs that have different bits in that position, which can be calculated as the product of the number of 1's and the number of 0's.

Here's the implementation of the bit manipulation approach:

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int n = nums.size();
        int totalHammingDist = 0;
        for (int i = 0; i < 32; i++) {  // iterate over bit positions
            int numOnes = 0, numZeros = 0;
            for (int j = 0; j < n; j++) {  // count number of 1's and 0's
                if ((nums[j] >> i) & 1)
                    numOnes++;
                else
                    numZeros++;
            }
            totalHammingDist += numOnes * numZeros;  // calculate hamming distance for current bit position
        }
        return totalHammingDist;
    }
};

In the above implementation, we have used two loops. The outer loop iterates over each bit position from 0 to 31 (as we are given that the maximum value of the input integers is 10^9). The inner loop counts the number of 1's and 0's in the current bit position for each integer in the array. We then calculate the number of pairs that have different bits in that position and add it to the totalHammingDist variable.

This implementation has a time complexity of O(32n) = O(n), making it much faster than the brute-force approach.

1