5-line O(N) time O(1) space, simply a math problem: sum ones*(N-ones) with detailed explanation

• Key observation: Total Hamming distance can be decomposed into contributions from each bit position, and we calculate each of them independently.

Consider each 32-bit integer `x`m=1:N as a 32D 0-1 vector: e.g.,
`x`1: [1, 1, 0, 0, 1, ..., 0, 1]
`x`2: [0, 1, 0, 0, 1, ..., 0, 0]
`x`3: [0, 0, 1, 0, 0, ..., 0, 1]
...
`x`N: [1, 0, 0, 0, 1, ..., 1, 1].

For each "column" `i` (i.e., `i`-position bit), we count the number of `1` bits `ones`i, then the contribution Hamming distance from `i`-position bit is simply

• `ones`i*(`N - ones`i).

Sum up all position `i` and we have the answer Σi=1:32`ones`i*(`N - ones`i). The times complexity is O(8N sizeof(`int`)).

``````    int totalHammingDistance(vector<int>& nums) {
int res = 0;
for (int i = 1, ones = 0; (ones = 0), i; i<<=1) {
for (int n:nums) if (n&i) ++ones;
res += ones*(nums.size()-ones);
}
return res;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.