Reference: LeetCode EPI 4.4
Difficulty: Medium

## Problem

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Refer to: 461. Hamming Distance or EPI 4.4

Note:

• Elements of the given array are in the range of 0 to 10^9.
• Length of the array will not exceed 10^4.

Example:

## Analysis

Methods:

1. Brute-Force (Time Limit Exceeded)
• Check all the unique pairs of elements for differing bits.
• xor of two bits 1 if they are not the same, and 0 otherwise.

Time: $O(N^2 \cdot \log{V}) \sim O(N^2)$ where $V$ is the largest value any of the elements can ever take. Since all elements are less than $10^9$, the value $\log{V}$ is approximately $30$, which is a small constant.
Space: $O(1)$

1. Combination / Pair
• For any particular bit position, count the number $k$ of elements with this bit ON / 1. Hence the number of elements with the bit OFF / 0 should be $(n - k)$.
• For each bit position (32 in total), we have $k$ 1 bits and $(n - k)$ 0 bits, and we want the total number of of combinations (pairs) of 1 and 0, which equals k * (n - k).
• Note: We can switch the order of loops to reduce space complexity like the code below.

Time: $O(N\log{V}) \sim O(N)$
Space: $O(\log{V})$ or $O(1)$

1. Vectorized Method
• Vectorized operations can result in small, elegant, and good performance code. It is supported in Python. The takeaway is that we don’t need the outer loop and instead we process every bit at the same time. For example:

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.