This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

I. Title Description:

Ii. Analysis of Ideas:

Duck rush, ten days in a row, the cylinder is almost in hand. What I want to share with you today is a medium topic, which is related to the topic we shared yesterday. Yesterday was the Hamming distance of two integers. Today I’m going to give you an array and find the sum of the Hamming distances between any two numbers in the array.

Violence make

To be honest, when you see the amount of data in this problem, 10 to the fourth, you just want to go brute force. Go through all the numbers in pairs, calling the hamming distance method in yesterday’s problem. Sure enough, there was no unexpected timeout.

Sum by bitwise traversal

Well, when we’re trying to figure out the Hamming distance, we’re trying to figure out the number of bits. We can iterate over 32 bits directly. For each bit, we find the number of 1s and 0s in the corresponding bits of all digits. The sum of the Hamming distances for this digit is the number of 1s multiplied by the number of 0s. And then the sum of all the bits is the result.

Iii. AC Code:

/ / timeout
class Solution {

    / * * *@param Integer[] $nums
     * @return Integer
     */
    function totalHammingDistance($nums) {
        $ret = 0;
        $len_n = count($nums);
        for ($i = 0; $i < $len_n; $i{+ +)for ($j = $i + 1; $j < $len_n; $j{+ +)$ret+ =$this->hammingDistance($nums[$i].$nums[$j]); }}return $ret;
    }

    protected function hammingDistance($x.$y)
    {
        $ret = 0;
        $temp = $x ^ $y;
        while ($temp) {
            $temp = $temp & ($temp - 1);
            $ret+ +;//echo $temp;
        }
        return $ret; }}// bitwise traversal
function totalHammingDistance($nums) {
        $ret = 0;
        $len_n = count($nums);
        for ($i = 0; $i < 32; $i{+ +)$zero = $one = 0;
            for ($j = 0; $j < $len_n; $j{+ +)if (($nums[$j] > >$i) & 1) {
                    $one+ +; }else {
                    $zero++;
                }
            }
            $ret+ =$zero * $one;
        }
        return $ret;
    }
Copy the code

Iv. Summary:

Bit operation, general violent ideas can not pass, you can consider by bit traversal, general integer 32 bits, often have a miracle effect. Similarly, if you only have lowercase letters, you can always make an array of 26 lengths.