# LeetCode 477: Total Hamming Distance

## Problem Restatement

We are given an integer array `nums`.

The Hamming distance between two integers is the number of bit positions where their binary representations are different.

We need to return the sum of Hamming distances over all pairs of integers in `nums`.

For example:

```text
nums = [4, 14, 2]
```

Their binary forms are:

```text
4  = 0100
14 = 1110
2  = 0010
```

Pair distances:

```text
HammingDistance(4, 14) = 2
HammingDistance(4, 2)  = 2
HammingDistance(14, 2) = 2
```

So the answer is:

```text
2 + 2 + 2 = 6
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | Sum of Hamming distances across all pairs |
| Pair rule | Each unordered pair is counted once |
| Constraint idea | Numbers fit within a fixed number of bits |

Function shape:

```python
def totalHammingDistance(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [4, 14, 2]
```

Binary view:

```text
4  = 0100
14 = 1110
2  = 0010
```

Compare each pair:

```text
4  vs 14: 0100 vs 1110 differs in 2 places
4  vs 2 : 0100 vs 0010 differs in 2 places
14 vs 2 : 1110 vs 0010 differs in 2 places
```

Answer:

```python
6
```

Example 2:

```python
nums = [4, 4, 4]
```

Every pair has equal numbers.

So every Hamming distance is `0`.

Answer:

```python
0
```

Example 3:

```python
nums = [0, 1]
```

Binary view:

```text
0 = 0
1 = 1
```

They differ in one bit.

Answer:

```python
1
```

## First Thought: Brute Force

The direct method is to compare every pair.

For each pair `(nums[i], nums[j])`, compute:

```python
nums[i] ^ nums[j]
```

XOR marks the differing bit positions with `1`.

Then count the number of `1` bits.

```python
class Solution:
    def totalHammingDistance(self, nums: list[int]) -> int:
        ans = 0
        n = len(nums)

        for i in range(n):
            for j in range(i + 1, n):
                ans += (nums[i] ^ nums[j]).bit_count()

        return ans
```

This is easy to write and correct for small inputs.

## Problem With Brute Force

If there are `n` numbers, there are about:

```text
n * (n - 1) / 2
```

pairs.

So the brute force method takes `O(n^2)` pair checks.

That becomes too slow when `nums` is large.

We need to avoid comparing each pair one by one.

## Key Insight

Hamming distance can be counted bit by bit.

At one bit position, a pair contributes `1` to the answer only when one number has bit `0` and the other number has bit `1`.

So for each bit position:

1. Count how many numbers have a `1` at that bit.
2. Count how many numbers have a `0` at that bit.
3. Multiply them.

If:

```text
ones = count of numbers with bit 1
zeros = count of numbers with bit 0
```

then this bit contributes:

```text
ones * zeros
```

Why?

Every number with `1` can pair with every number with `0`.

Each such pair differs at this bit.

For `nums = [4, 14, 2]`:

```text
4  = 0100
14 = 1110
2  = 0010
```

Look at each bit column:

| Bit value | Bits from numbers | Ones | Zeros | Contribution |
|---|---|---:|---:|---:|
| `1` | `0, 0, 0` | 0 | 3 | 0 |
| `2` | `0, 1, 1` | 2 | 1 | 2 |
| `4` | `1, 1, 0` | 2 | 1 | 2 |
| `8` | `0, 1, 0` | 1 | 2 | 2 |

Total:

```text
0 + 2 + 2 + 2 = 6
```

## Algorithm

Set `ans = 0`.

For each bit position from `0` to `30`:

1. Count how many numbers have that bit set.
2. Let `ones` be that count.
3. Let `zeros = len(nums) - ones`.
4. Add `ones * zeros` to `ans`.

Return `ans`.

We use 30 or 31 bit positions depending on constraints. In Python, using 31 positions is safe for common LeetCode integer constraints here.

## Correctness

Consider any fixed bit position.

A pair contributes `1` to the Hamming distance at this position exactly when the two numbers have different bits at this position.

There are only two possible bit values: `0` and `1`.

If `ones` numbers have bit `1`, and `zeros` numbers have bit `0`, then every mixed pair contributes once. The number of mixed pairs is:

```text
ones * zeros
```

Pairs where both bits are `0` contribute nothing at this position.

Pairs where both bits are `1` also contribute nothing at this position.

Therefore, `ones * zeros` is exactly the total contribution of this bit position across all pairs.

The algorithm repeats this for every relevant bit position. Hamming distance is the sum of differences over all bit positions, so summing the contribution of every bit gives the total Hamming distance over all pairs.

Thus the algorithm returns the required answer.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(31n)` = `O(n)` | We scan all numbers once for each fixed bit position |
| Space | `O(1)` | Only counters are stored |

The number of checked bit positions is fixed, so the algorithm is linear in the length of `nums`.

## Implementation

```python
class Solution:
    def totalHammingDistance(self, nums: list[int]) -> int:
        ans = 0
        n = len(nums)

        for bit in range(31):
            ones = 0

            for num in nums:
                if num & (1 << bit):
                    ones += 1

            zeros = n - ones
            ans += ones * zeros

        return ans
```

## Code Explanation

We keep the total answer here:

```python
ans = 0
```

Then we check each bit position:

```python
for bit in range(31):
```

For each bit position, count how many numbers have that bit set:

```python
if num & (1 << bit):
    ones += 1
```

The expression:

```python
1 << bit
```

creates a mask with only that bit turned on.

For example:

| `bit` | `1 << bit` | Binary |
|---:|---:|---|
| 0 | 1 | `0001` |
| 1 | 2 | `0010` |
| 2 | 4 | `0100` |
| 3 | 8 | `1000` |

After counting `ones`, we compute:

```python
zeros = n - ones
```

Then this bit contributes:

```python
ones * zeros
```

Finally, return the total:

```python
return ans
```

## More Compact Implementation

Python can count `ones` with a generator expression:

```python
class Solution:
    def totalHammingDistance(self, nums: list[int]) -> int:
        ans = 0
        n = len(nums)

        for bit in range(31):
            ones = sum((num >> bit) & 1 for num in nums)
            ans += ones * (n - ones)

        return ans
```

This version uses the same idea.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.totalHammingDistance([4, 14, 2]) == 6
    assert s.totalHammingDistance([4, 4, 4]) == 0
    assert s.totalHammingDistance([0, 1]) == 1
    assert s.totalHammingDistance([0, 0, 1, 1]) == 4
    assert s.totalHammingDistance([1, 2, 3]) == 4

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[4, 14, 2]` | Main example |
| `[4, 4, 4]` | All numbers equal |
| `[0, 1]` | Small pair with one differing bit |
| `[0, 0, 1, 1]` | Duplicate values with multiple cross pairs |
| `[1, 2, 3]` | Several bits contribute independently |