Сложность: easy
Дано положительное целое число n, найдите и верните наибольшее расстояние между любыми двумя соседними единицами в двоичном представлении числа n. Если нет двух соседних единиц, верните 0.
Две единицы считаются соседними, если их разделяют только нули (возможно, никаких нулей нет). Расстояние между двумя единицами — это абсолютная разница между их позициями в битовом представлении. Например, две единицы в "1001" имеют расстояние 3.
Пример:
Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.
👨💻 Алгоритм:
1⃣Создайте список A индексов i, таких что в двоичном представлении числа n i-й бит установлен в 1.
2⃣Используйте список A, чтобы найти максимальное расстояние между соседними значениями. Для этого пройдите по списку и вычислите разницу между каждым соседним элементом.
3⃣Верните найденное максимальное расстояние.
😎 Решение:
class Solution {
function binaryGap($N) {
$A = [];
for ($i = 0; $i < 32; $i++)
if (($N >> $i) & 1) $A[] = $i;
$ans = 0;
for ($i = 0; $i < count($A) - 1; $i++)
$ans = max($ans, $A[$i + 1] - $A[$i]);
return $ans;
}
}Ставь 👍 и забирай 📚 Базу знаний