Total Hamming Distance
mediumTime: O(32n)Space: O(1)
Signals to notice
total Hamming distance across all pairsper-bit countingc × (n-c) per bit
Brute force first
Check every pair — O(n²).
The key insight
For each of 32 bits: count numbers with 1 (c). Contribution = c × (n-c). Sum all bits. O(32n).
What must stay true
Per-bit contribution = number of 1-0 pairs = c × (n-c).
Easy way to go wrong
Computing per-pair — per-bit counting avoids quadratic work.