algoadvance

Leetcode 477. Total Hamming Distance

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 the array.

Example:

Input: nums = [4, 14, 2]
Output: 6
Explanation: There are 3 pairs (4, 14), (4, 2), and (14, 2) with respective Hamming distances 2, 2, and 2; thus the sum is 6.

Constraints:

• The number of elements in nums is in the range [1, 10^4].
• Each integer in nums will be in the range [0, 10^9].

Clarifying Questions

1. Can nums contain duplicate numbers?
   • Since there are no restrictions against duplicates in the constraints, yes, nums can contain duplicate numbers.
2. Can nums be empty?
   • No, the minimum size of nums is 1 based on constraints.

Strategy

1. Brute-force Approach: Compute the Hamming distance for every pair and sum them. This is straightforward but inefficient for large arrays.
2. Optimized Approach: Utilize bit manipulation to compute Hamming distances in a more efficient manner.
   • For each bit position, count how many numbers have a 1 at this position and how many have 0.
   • The Hamming distance contributed by this bit position is the product of these two counts (since a 1 and a 0 at the same position between any two numbers contribute 1 to the Hamming distance).

Code

#include <vector>
using namespace std;

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int total = 0, n = nums.size();
        
        for (int i = 0; i < 32; i++) {
            int countOnes = 0;
            for (int num : nums) {
                if (num & (1 << i)) {
                    countOnes++;
                }
            }
            int countZeros = n - countOnes;
            total += countOnes * countZeros;
        }
        
        return total;
    }
};

Explanation

1. Initialize total to 0 and get the size of nums.
2. Loop over each of the 32 bit positions (since a max range of 10^9 can be represented in 32 bits).
3. For each bit position i:
   • Count how many numbers have a 1 at bit position i (countOnes).
   • The other numbers must have a 0 at bit position i, so countZeros is n - countOnes.
   • The contribution to the Hamming distance from bit position i is countOnes * countZeros.
   • Add this contribution to total.
4. Return total.

Time Complexity

• Time Complexity: O(32 * n) = O(n), where n is the number of elements in the input array.
  • Looping over 32 bit positions is constant time, and for each bit position, we loop through the array once.
• Space Complexity: O(1), since we are using a constant amount of additional space regardless of the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?