Total Hamming Distance - Video Solutions

Problem Overview: Given an integer array nums, compute the sum of Hamming distances for every pair of numbers. The Hamming distance between two integers is the number of bit positions where their binary representations differ.

This problem mixes array iteration with bit manipulation. A direct pairwise comparison works but becomes slow as the array grows. The key observation: Hamming distance is determined independently at each bit position.

Approach 1: Naive Pairwise Calculation (O(n² * B) time, O(1) space)

The straightforward approach checks every pair of numbers in the array. For each pair (i, j), compute the Hamming distance using XOR: x ^ y. The number of set bits in the result tells you how many positions differ. Use a loop or built-in popcount operation to count set bits. Accumulate the distance for all pairs.

This method relies only on simple math and bit operations, making it easy to understand and implement. However, it requires comparing n(n-1)/2 pairs, which quickly becomes expensive for large arrays. With n = 10^4, the quadratic growth makes it impractical. Still useful for verifying correctness or when input sizes are small.

Approach 2: Bit-by-Bit Contribution (O(n * 32) time, O(1) space)

The optimal solution flips the perspective. Instead of examining pairs, analyze each bit position independently. For a given bit index b, count how many numbers have that bit set (ones) and how many do not (zeros). Every pair consisting of one number with bit 1 and one with bit 0 contributes exactly one to the Hamming distance.

The number of such pairs is ones * zeros. Add this value to the total for that bit. Repeat for all 32 bit positions in a standard integer. Each iteration scans the array once and checks the bit using (num >> b) & 1. This converts the quadratic pairwise computation into a linear scan multiplied by the number of bits.

This works because bit positions contribute independently to the Hamming distance. Instead of evaluating every pair, you count how many pairs differ at each position in aggregate. The result is a time complexity of O(n * 32), which simplifies to O(n) for fixed-width integers.

Recommended for interviews: Interviewers expect the bit-by-bit counting approach. The brute-force pairwise method demonstrates understanding of XOR and Hamming distance, but the optimized solution shows you can recognize independent bit contributions and reduce quadratic work to linear time. Most accepted production solutions use the bit counting technique.