Задача: 477. Total Hamming Distance
Сложность: Medium

Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются.
Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums.

Пример:
Input: nums = [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).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

👨‍💻 Алгоритм:

1⃣Для каждой уникальной пары элементов из массива вычисляем битовое XOR, чтобы найти позиции, где биты различаются. Бит, равный 1 в результате, указывает на различие.

2⃣Для каждой пары элементов используем XOR, чтобы получить битовую разницу, и подсчитываем количество битов, равных 1, чтобы определить Хэммингово расстояние между парой.

3⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний.

😎 Решение:
class Solution {
function totalHammingDistance($nums) {
$ans = 0;

if (empty($nums)) {
return $ans;
}

for ($i = 0; $i < count($nums) - 1; $i++) {
for ($j = $i + 1; $j < count($nums); $j++) {
$ans += $this->countBits($nums[$i] ^ $nums[$j]);
}
}

return $ans;
}

private function countBits($n) {
$count = 0;
while ($n > 0) {
$count += $n & 1;
$n >>= 1;
}
return $count;
}
}

Ставь 👍 и забирай 📚 Базу знаний