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:**

1 | Input: 4, 14, 2 |

## Analysis

**Methods:**

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.1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20public int totalHammingDistance(int[] nums) {

int n = nums.length;

int count = 0;

for (int i = 0; i < n; ++i) {

for (int j = i + 1; j < n; ++j) {

count += hammingDistance(nums[i], nums[j]);

}

}

return count;

}

private int hammingDistance(int x, int y) {

int xor = x ^ y;

int count = 0;

while (xor != 0) {

xor = xor & (xor - 1);

count += 1;

}

return count;

}**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)$

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.1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21// 0 1 0 0 -> 4

// 1 1 1 0 -> 14

// 0 0 1 0 -> 2

// -----------------

// ON: 1 2 2 0

// OFF: 2 1 1 3

// 2 2 2 0 <--- # combination = 6

public int totalHammingDistance(int[] nums) {

int n = nums.length;

int sum = 0;

for (int i = 0; i < 32; ++i) { // outer loop

int onCount = 0;

for (int val : nums) {

val = (val >> i) & 1; // isolate the bit on the lsd position

onCount += val & 1; // 1&1=1 0&1=0

// onCount += val ^ 0; // 1^0=1 0^0=0

}

sum += onCount * (n - onCount); // combination calculation

}

return sum;

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

- For any particular bit position, count the number $k$ of elements with this bit
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:
1

2

3

4

5

6count = [0 0 0 0];

for (int val : nums) {

// val is like [0 1 0 0]

count += val; // [0 0 0 0] + [0 1 0 0] = [0 1 0 0]

}

return sum(count); // sum([2 2 2 0]) = 6

- 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: