• 45.9%

https://leetcode.com/problems/total-hamming-distance/

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.

Note:

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

https://discuss.leetcode.com/topic/72092/java-o-n-time-o-1-space

Java O(n) time O(1) Space

For each bit position 1-32 in a 32-bit integer, we count the number of integers in the array which have that bit set. Then, if there are n integers in the array and k of them have a particular bit set and (n-k) do not, then that bit contributes k* (n-k) hamming distance to the total.

https://discuss.leetcode.com/topic/72099/share-my-o-n-c-bitwise-solution-with-thinking-process-and-explanation

Share my O(n) C++ bitwise solution with thinking process and explanation

1. Problem

The problem is to find the total Hamming distance between all pairs of the given numbers.

2. Thinking process

2.1 For one pair

When you calculate Hamming distance between x and y, you just

calculate p = x ^ y;
count the number of 1’s in p
The distance from x to y is as same as y to x.

2.2 Trival approach

For a series of number: a1, a2, a3,…, an

Use the approach in 2.1
(suppose distance(x, y) is the Hamming distance between x and y):

For a1, calculate S(1) = distance(a1, a2)+distance(a1, a3)+ … +distance(a1, an)
For a2, calculate S(2) = distance(a2, a3)+distance(a2, a4)+ … +distance(a2, an)
……
For a(n - 1), calculate S(n - 1) = distance(a(n - 1), a(n))

Finally , S = S(1) + S(2) + … + S(n - 1).

The function distance is called 1 + 2 + … + (n - 1) = n(n - 1)/2 times! That’s too much!

2.3 New idea

The total Hamming distance is constructed bit by bit in this approach.

Let’s take a series of number: a1, a2, a3,…, an

Just think about all the Least Significant Bit (LSB) of a(k) (1 ≤ k ≤ n).

How many Hamming distance will they bring to the total?

If a pair of number has same LSB, the total distance will get 0.

If a pair of number has different LSB, the total distance will get 1.

For all number a1, a2, a3,…, a(n), if there are p numbers have 0 as LSB (put in set M), and q numbers have 1 for LSB (put in set N).

There are 2 situations:

Situation 1. If the 2 number in a pair both comes from M (or N), the total will get 0.

Situation 2. If the 1 number in a pair comes from M, the other comes from N, the total will get 1.

Since Situation 1 will add NOTHING to the total, we only need to think about Situation 2

How many pairs are there in Situation 2?

We choose 1 number from M (p possibilities), and 1 number from N (q possibilities).

The total possibilities is p × q = pq, which means

The total Hamming distance will get pq from LSB.

If we remove the LSB of all numbers (right logical shift), the same idea can be used again and again until all numbers becomes zero

2.4 Time Complexity

In each loop, we need to visit all numbers in nums to calculate how many numbers has 0 (or 1) as LSB.

If the biggest number in nums[] is K, the total number of loop is [logM] + 1.

So, the total time complexity of this approach is O(n).

3. Code

#### python

https://discuss.leetcode.com/topic/72149/python-via-strings

Python via Strings

https://discuss.leetcode.com/topic/72095/python-explanation

Python Explanation

Notice the total hamming distance is the sum of the total hamming distance for each of the i-th bits separately.

So, let’s consider the i-th column, which consists of numbers chosen from {0, 1}. The total hamming distance would be the number of pairs of numbers that are different. That is,

Total hamming distance for the i-th bit =

(the number of zeros in the i-th position) *

(the number of ones in the i-th position).

Code:

https://discuss.leetcode.com/topic/72190/python-o-nlogv-time

Python O(nlogV) time

Just calculate combinations vertically.

#### java

https://discuss.leetcode.com/topic/72104/java-solution-with-explanation

Java Solution with Explanation

The first solution came to my mind is brute forcely iterate through each pair, then sum all Integer.bitCount(x ^ y) like what I mentioned here https://discuss.leetcode.com/topic/72093/java-1-line-solution-d But as you can imagine, it TLE…

Let’s think about this problem another way. We can separate the calculation to do one bit at a time. For example, look at the rightmost bit of all the numbers in nums. Suppose that i numbers have a rightmost 0-bit, and j numbers have a 1-bit. Then out of the pairs, i j of them will have 1 in the rightmost bit of the XOR. This is because there are i j ways to choose one number that has a 0-bit and one that has a 1-bit. These bits will therefore contribute i * j towards the total of all the XORs.

Apply above algorithm to each bit (31 bits in total as specified in the problem), sum them together then we get the answer.