The Hamming distance of two integers refers to the number of bits corresponding to the binary number of these two numbers.
Calculate the sum of the Hamming distances between any two numbers in an array.
Example
Input: 4, 14, 2
Output: 6
Explanation: In the binary representation, 4 is represented as 0100, 14 is represented as 1110, and 2 is represented as 0010. (This is to reflect the relationship between the last four digits)
So the answer is: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Notice:
The range of elements in the array is from 0 to 10^9. The length of the array shall not exceed 10^4.
Problem-solving ideas
Exhausting the number of combinations of two and two, and then adding up the distance between Hamming is the simplest and straightforward solution.
The result is that when a large amount of data is used, the number of factorials will be too large.
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function totalHammingDistance($nums) {
$count = count($nums);
$sum = 0;
for ($i = 0; $i < $count - 1; $i++) {
for ($j = $i+1; $j < $count; $j++)
{
$sum += $this->hm($nums[$i], $nums[$j]);
}
}
return $sum;
}
// Hanming distance method function hm($x, $y)
{
return substr_count(decbin($x ^ $y), '1');
}}
Expanded ideas:
Expand the problem-solving ideas
We often analyze problems like this: the simplest situation -> the usual, complicated situation. In the past we were: traversing all possible combinations of pairs.
Now let’s look at it from another perspective: if int has only 1 bit -> int has 32 bits. leetcode
First, if int has only 1 bit, that is, there are only two types of elements in the array nums, 0 or 1, the steps to find the Hanming distance sum are as follows: get
First divide the array into two groups of dividends, one group of 0 digits, one group of 1 digits
Combine two groups of numbers in pairs, one is a and the other is b
If a and b are both from 0, or both from 1, there will be no Hanming distance generated at this time. But if one is from the group 0 and the other is from the group 1, the distance will be generated
Assuming that the number of elements in the nums array is n, where the number of elements 0 is k, then the number of elements 1 is n-k, then the sum of the distances of Hamming can be produced in the previous step is k*(n-k)
k*(n-k) is the total distance sum of Hamming when int is only 1 bit
If the number of bits of int is expanded from 1 bit to 32 bits, then each bit will be traversed, and then the Hamming distance sum on this bit will be calculated and accumulated to one piece. This will reduce the algorithm complexity from $O(N^2)$ to $O(32\\times N)$, which is $O(N)$.
You can see the following example:
Decimal Binary
4: 0 1 0 0
14: 1 1 1 0
2: 0 0 1 0
1: 0 0 0 1
Let’s look at the last column first, with three 0s and one 1, then the distance between them is 3, that is, the distance between 1 and the other three 0s is accumulated, and then look at the third column, the accumulated distance between the Hamming is 4, because each 1 will generate two Hamming distances with two 0s, and the second column is also 4, and the first column is 3. The sum of Hamming distances combined with each column is the sum of the numbers 0 and 1 of each column. The sum of Hamming distances of each column is the sum of Hamming distances between the nums elements in the array as found in the question.
Code
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function totalHammingDistance($nums) {
$count = count($nums);
$sum = 0;
for($i = 0; $i < 32; $i++)
{
$tmpCount = 0;
for($j = 0; $j < $count; $j++)
$tmpCount += ($nums[$j] >> $i) & 1;
}
$sum += $tmpCount * ($count - $tmpCount);
}
return $sum;
}
}
This is the article about this example explanation of php calculating the sum of Hanming distances. For more related methods for php calculating the sum of Hanming distances, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!