Key word: Hamming distance, Array of numbers, Hamming distance between each pair.

Requirement: Find the total hamming distance.

Brute force: For each pair of number, calculate their hamming distance, Time complexity is O(n^2).

Improved method:

**Vertically**take a look at the bits at a given position across all the numbers.- Every bit is either one or zero, let`s say we have x set bits and y unset bits, the total pairs that can generate a distance of 1 at this position is x*y.
- Apply the above calculation to all bits and sum up the total distance.
- Time complexity is O(n) and space complexity is O(1).

```
public class Solution {
public int totalHammingDistance(int[] nums) {
int total = 0;
int mask = 1;
for (int i = 0; i < 32; i++) {
int setBit = 0;
for (int j : nums) {
setBit += (j & mask) == 0 ? 0 : 1;
}
total += setBit * (nums.length - setBit);
mask <<= 1;
}
return total;
}
}
```