algoadvance

Leetcode 477. Total Hamming Distance

Problem Statement

Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Clarifying Questions

1. Range of inputs: What are the constraints on the size of the input array (nums) and the values within the array?
   • Typically, nums.length can range from 1 to 10^4 and values in nums can be as large as 10^9.
2. Input and Output Format:
   • Input: An integer array nums.
   • Output: An integer representing the total Hamming distance.
3. Edge Cases:
   • Single element array.
   • Array with all elements being the same.

Strategy

1. Brute Force Approach:
   • Calculate the Hamming distance for every pair of elements.
   • Time Complexity: O(N^2 * M) where N is the length of nums and M is the number of bits (around 30 for integers up to 10^9).
   • This approach is not efficient for large inputs.
2. Efficient Approach:
   • For each bit position from 0 to 30, count how many numbers have that bit set to 1 and how many have it set to 0.
   • For each bit position, the Hamming distance contribution is the product of these counts.
   • Sum up the contributions from all bit positions for the result.
   • Time Complexity: O(N * 30), which simplifies to O(N).

Code

Here’s the implementation of the efficient approach:

public class Solution {
    public int totalHammingDistance(int[] nums) {
        int total = 0;
        int n = nums.length;
        
        // There are 30 bits to consider (since numbers are <= 10^9)
        for (int i = 0; i < 30; ++i) {
            int countOne = 0;
            for (int num : nums) {
                countOne += (num >> i) & 1;
            }
            int countZero = n - countOne;
            total += countOne * countZero;
        }
        
        return total;
    }
}

Time Complexity

• Efficient approach: O(N) where N is the length of the nums array. This is because for each of the 30 bit positions, we are iterating through the array once.
• Space Complexity: O(1), since we are only using a fixed amount of extra space.

This solution efficiently computes the total Hamming distance by leveraging bit manipulation and avoids the quadratic time complexity of the brute-force approach.

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?