Задача с собеседования в

Задача с собеседования в eBay Дано целое положительное число n, найдите и верните максимальное расстояние между любыми двумя соседними единицами в его двоичном представлении. Если в числе нет двух соседних единиц, верните 0. Две единицы считаются соседними , если между ними находятся только нули (возможно, ни одного нуля). Расстояние между двумя единицами - это абсолютная разность между их битовыми позициями. Например, расстояние между двумя единицами в "1001" равняется 3. Пример 1: Input: n = 22 Output: 2 Explanation: 22 в двоичном представлении - "10110". Первая пара соседних единиц: " 1 0 1 10" с расстоянием 2. Вторая пара соседних единиц: "10 11 0" с расстоянием 1. Ответ - наибольшее из этих двух расстояний, то есть 2. Обратите внимание, что пара " 1 01 1 0" не является допустимой, так как между подчёркнутыми единицами стоит ещё одна единица, разделяющая их. Пример 2: Input: n = 8 Output: 0 Explanation: 8 в двоичном представлении - "1000". В двоичном представлении числа 8 нет ни одной пары соседних единиц, поэтому возвращаем 0. Пример 3: Input: n = 5 Output: 2 Explanation: 5 в двоичном представлении - "101". Ограничения: 1 <= n <= 10⁹ НАШ ЧАТ АЛГОРИТМИСТОВ Решение Итак, необходимо найти максимальную разность между соседними единицами. Заметим, что нам не нужно хранить все позиции, достаточно обновлять позицию последней встреченной единицы (last_pos), чтобы при встрече следующей вычислить расстояние между ними. Соседство единиц гарантируется тем, что last_pos обновляется только на единицах ; если текущий бит - ноль, last_pos не меняется. Соответственно, когда встречаем следующую единицу, она является ближайшей (т.е. соседней) к последней встреченной. Заводим переменные: max_gap - для хранения максимального расстояния; инициализируем как 0 (если в числе нет соседних единиц, вернём 0) current_pos - текущая позиция бита; начинаем с младшего (0) last_pos - позиция последней встреченной единицы; изначально -1, так как ещё нет ни одной обработанной единицы. Пока в n есть хотя бы один необработанный бит, проходим от младшего бита к старшему (справа налево): - Проверяем, является ли текущий бит единицей с помощью операции побитового И: если (n & 1) == 1, значит, бит равен единице. - Если это единица, и единица уже встречалась ранее (last_pos != -1): - обновляем max_gap, если расстояние между текущей позицией бита и позицией последней встреченной единицы (current_pos - last_pos) больше текущего. - Запоминаем текущую позицию как "последнюю встреченную единицу". Таким образом, следующая единица будет сравниваться с этой. - В конце итерации: - сдвигаем n вправо на один бит (с помощью операции n >>= 1 отбрасываем обработанный младший бит, следующий бит становится младшим); - увеличиваем текущую позицию на 1. Когда n обнулилось (не осталось ни одного бита), возвращаем max_gap, хранящий накопленный максимум. Сложность O(log n) - по времени (кол-во итераций равняется кол-ву бит в числе) O(1) - по памяти (храним некоторое кол-во переменных) Код class Solution: def binaryGap(self, n: int) -> int: max_gap = 0 current_pos = 0 last_pos = -1 while n: if n & 1: if last_pos != -1: max_gap = max(max_gap, current_pos - last_pos) last_pos = current_pos n >>= 1 current_pos += 1 return max_gap @algoses