477. Total Hamming Distance

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

1
2
3
4
5
6
7
8
Example:
Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

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.

方法一:

每一位,只有一个是0,一个是1,才会有效果。

所以统计每一位中1个个数和0的个数

每一位个数的乘积和就是答案

优化,1的个数和0的个数相加等于固定长度,所以只要统计一个就可以了。

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
vector<int> ones(32, 0);
vector<int> zeros(32, 0);
int flag = 1;
for(int i=0; i<32; i++){
for(auto num:nums){
if(num&flag){
ones[i]++;
}else{
zeros[i]++;
}
}
flag <<= 1;
}
int res = 0;
for(int i=0; i<32; i++)
res += ones[i] * zeros[i];
return res;
}
};

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.

1
2
3
4
5
6
7
8
9
10
public int totalHammingDistance(int[] nums) {
int total = 0, n = nums.length;
for (int j=0;j<32;j++) {
int bitCount = 0;
for (int i=0;i<n;i++)
bitCount += (nums[i] >> j) & 1;
total += bitCount*(n - bitCount);
}
return 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int size = nums.size();
if(size < 2) return 0;
int ans = 0;
int *zeroOne = new int[2];
while(true)
{
int zeroCount = 0;
zeroOne[0] = 0;
zeroOne[1] = 0;
for(int i = 0; i < nums.size(); i++)
{
if(nums[i] == 0) zeroCount++;
zeroOne[nums[i] % 2]++;
nums[i] = nums[i] >> 1;
}
ans += zeroOne[0] * zeroOne[1];
if(zeroCount == nums.size()) return ans;
}
}
};

python


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

Python via Strings

1
2
def totalHammingDistance(self, nums):
return sum(b.count('0') * b.count('1') for b in zip(*map('{:032b}'.format, nums)))

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

We then add all of these together to get our answer.

Code:

1
2
3
4
5
6
bits = [ [0,0] for _ in xrange(32) ]
for x in A:
for i in xrange(32):
bits[i][x%2] += 1
x /= 2
return sum( x*y for x,y in bits )

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

Python O(nlogV) time

Just calculate combinations vertically.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def totalHammingDistance(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = 0
mask = 1
for j in range(0, 32):
ones = zeros = 0
for num in nums:
if num & mask:
ones += 1
else:
zeros += 1
ans += ones * zeros
mask = mask << 1
return ans

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.

Reference: http://stackoverflow.com/questions/21388448/sum-of-xor-values-of-all-pairs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public int totalHammingDistance(int[] nums) {
int n = 31;
int len = nums.length;
int[] countOfOnes = new int[n];
for (int i = 0; i < len; i++) {
for (int j = 0; j < n; j++) {
countOfOnes[j] += (nums[i] >> j) & 1;
}
}
int sum = 0;
for (int count: countOfOnes) {
sum += count * (len - count);
}
return sum;
}
}
谢谢你,可爱的朋友。