Total Hamming Distance
mediumTime: O(32n)Space: O(1)
Recognize the pattern
total Hamming distance across all pairsper-bit countingc × (n-c) per bit
Brute force idea
Check every pair — O(n²).
Better approach
For each of 32 bits: count numbers with 1 (c). Contribution = c × (n-c). Sum all bits. O(32n).
Key invariant
Per-bit contribution = number of 1-0 pairs = c × (n-c).
Watch out for
Computing per-pair — per-bit counting avoids quadratic work.