Total Hamming Distance

Total Hamming Distance

What is this problem about?

The "Total Hamming Distance coding problem" is a fascinating bitwise analysis challenge. The Hamming distance between two integers is the number of positions at which the corresponding bits are different. In this problem, you are given an array of integers and asked to find the sum of Hamming distances between all possible pairs of numbers in the array. Since the number of pairs grows quadratically with the size of the array, a naive $O(n^2)$ approach will be too slow, and a more efficient bit-by-bit approach is required.

Why is this asked in interviews?

This "Total Hamming Distance interview question" is a staple at companies like Microsoft and Meta because it tests a candidate's ability to optimize an algorithm by changing the perspective of the problem. Instead of looking at pairs of numbers, you look at individual bit positions. This leap from "pair-wise processing" to "feature-wise processing" is a critical skill for optimizing large-scale computations in fields like error correction, bioinformatics, and data compression.

Algorithmic pattern used

The "Array, Math, Bit Manipulation interview pattern" is used to solve this in linear time, $O(32n)$ or simply $O(n)$. We iterate through each of the 32 bit positions (since integers are typically 32-bit). For each bit position, we count how many numbers in the array have a '1' at that position and how many have a '0'. The number of pairs that differ at this specific bit position is simply the product of these two counts. Summing these products across all 32 bit positions gives the total Hamming distance.

Example explanation

Consider the array [4, 14, 2]. In binary:

• 4: 0 1 0 0
• 14: 1 1 1 0
• 2: 0 0 1 0

Bit positions (from right to left):

• Pos 0: All are 0. Pairs = 0 * 3 = 0.
• Pos 1: Two '1's (14, 2), one '0' (4). Pairs = 2 * 1 = 2.
• Pos 2: Two '1's (4, 14), one '0' (2). Pairs = 2 * 1 = 2.
• Pos 3: One '1' (14), two '0's (4, 2). Pairs = 1 * 2 = 2. Total Hamming Distance = 0 + 2 + 2 + 2 = 6.

Common mistakes candidates make

A common mistake in the "Total Hamming Distance interview question" is trying to calculate the Hamming distance for every pair using a nested loop. This leads to $O(n^2)$ complexity, which is inefficient for large arrays. Another error is not correctly handling bitwise operations, such as forgetting the precedence of operators or failing to check all 31 or 32 bits of the integer.

Interview preparation tip

To excel in the "Array, Math, Bit Manipulation interview pattern," practice "thinking bit-wise." Many bit manipulation problems that seem complex on a per-number basis become much simpler when you analyze each bit position independently. Understanding the properties of XOR and how bits contribute to sums is also very helpful.