#477

Medium

LeetCode Problem Workspace

Total Hamming Distance

Calculate the total Hamming distance between all pairs in an integer array using efficient bit manipulation techniques.

Problem Statement

The Hamming distance between two integers is the number of positions at which their corresponding bits differ. Given an array of integers, the task is to calculate the sum of Hamming distances between all pairs of integers in the array.

For example, with an array nums = [4, 14, 2], you calculate the pairwise Hamming distances between each combination of numbers and sum them. The Hamming distance between two numbers is computed by comparing the binary representation of the numbers bit by bit.

Examples

Example 1

Input: nums = [4,14,2]

Output: 6

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

Example details omitted.

Constraints

1 <= nums.length <= 104
0 <= nums[i] <= 109
The answer for the given input will fit in a 32-bit integer.

Solution Approach

Brute Force Approach

A straightforward approach is to iterate through every pair of integers in the array, calculate the Hamming distance for each pair, and sum them. However, this approach is inefficient for larger arrays due to its O(n^2) time complexity.

Optimized Bitwise Approach

To optimize, focus on the individual bits of the numbers. Count the number of 1s and 0s at each bit position across all numbers, and calculate the Hamming distance based on how often a 1 appears in one number and a 0 in another. This reduces the time complexity to O(n * 32).

Parallel Bit Counting

For even greater efficiency, use parallel bit counting techniques to simultaneously process all bit positions. This approach takes advantage of the fact that we can compute bitwise distances for multiple bits at once, further optimizing the performance.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The brute force approach has a time complexity of O(n^2), where n is the length of the array. The optimized approach, which processes each bit individually, has a time complexity of O(n * 32) because there are up to 32 bits per number. The space complexity is O(1) for both approaches since we only store the number of 1s and 0s per bit position during computation.

What Interviewers Usually Probe

The candidate should demonstrate familiarity with bit manipulation and array traversal.
Look for an understanding of time complexity optimization when discussing larger input sizes.
Expect the candidate to recognize the inefficiencies of a brute force solution and propose an optimized approach.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the definition of Hamming distance and incorrectly comparing non-corresponding bits.
Failure to optimize the brute force solution, resulting in an inefficient approach for larger arrays.
Incorrect handling of edge cases, such as arrays with very small or very large values.

Follow-up variants

Calculate Hamming distance for a fixed number of integers instead of all pairs.
Modify the problem to calculate the Hamming distance between a given set of numbers and a target number.
Optimize for extremely large arrays, aiming for constant time solutions based on preprocessed bit counts.

FAQ

What is the Hamming distance?

The Hamming distance between two integers is the number of bit positions where their binary representations differ.

How do you calculate the Total Hamming Distance efficiently?

Instead of calculating pairwise Hamming distances directly, you can optimize by counting how often a particular bit is 1 in the array and using that to compute the total distance.

What is the time complexity of the optimized solution for the Total Hamming Distance problem?

The optimized solution has a time complexity of O(n * 32), where n is the length of the array and 32 is the maximum number of bits for any number.

What is the primary pattern used to solve the Total Hamming Distance problem?

The primary pattern is array manipulation combined with bitwise operations, allowing for efficient computation of Hamming distances.

How does GhostInterview help solve this problem?

GhostInterview provides solutions that focus on bit manipulation to reduce time complexity and optimize for larger input sizes, ensuring efficient problem-solving.

terminal

Solution

Solution 1: Bit Manipulation

We enumerate each bit in the range $[0, 31]$. For the current enumerated bit $i$, we count the number of numbers where the $i$-th bit is $1$, denoted as $a$. Therefore, the number of numbers where the $i$-th bit is $0$ is $b = n - a$, where $n$ is the length of the array. In this way, the sum of the Hamming distance on the $i$-th bit is $a \times b$. We add the Hamming distances of all bits to get the answer.

1

2

3

4

5

6

7

8

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(32):
            a = sum(x >> i & 1 for x in nums)
            b = n - a
            ans += a * b
        return ans

Continue Practicing

#268 missing number #782 transform to chessboard #805 split array with same average