Боталка(Студенты) — Поступашки

Задача с собеседования в Persistent Systems Инвертирование бита числа x - это выбор какого-либо бита в двоичном представлении числа x и изменение его значения с 0 на 1 или с 1 на 0. Например, для x = 7 двоичное представление - 111, и мы можем выбрать любой бит (включая ведущие нули, которые не показаны) и инвертировать его. Мы можем инвертировать первый бит справа, чтобы получить 110, инвертировать второй бит справа, чтобы получить 101, инвертировать пятый бит справа (ведущий ноль), чтобы получить 10111, и так далее. Даны два целых числа start и goal. Верните минимальное количество инвертирований битов, чтобы преобразовать start в goal. Пример 1: Input: start = 10, goal = 7 Output: 3 Explanation: Двоичное представление 10 и 7 - это 1010 и 0111, соответственно. Мы можем преобразовать 10 в 7 за 3 шага: - Инвертировать первый бит справа: 1010 -> 1011. - Инвертировать третий бит справа: 1011 -> 1111. - Инвертировать четвёртый бит справа: 1111 -> 0111. Можно показать, что преобразовать 10 в 7 менее чем за 3 шага невозможно. Следовательно, возвращаем 3. Пример 2: Input: start = 3, goal = 4 Output: 3 Explanation: Бинарное представление 3 и 4 - это 011 и 100, соответственно. Мы можем преобразовать 3 в 4 за 3 шага: - Инвертировать первый бит справа: 011 -> 010. - Инвертировать второй бит справа: 010 -> 000. - Инвертировать третий бит справа: 000 -> 100. Можно показать, что преобразовать 3 в 4 менее чем за 3 шага невозможно. Следовательно, возвращаем 3. Ограничения: 0 <= start, goal <= 10⁹ НАШ ЧАТ АЛГОРИТМИСТОВ Решение И вновь задачка на побитовые манипуляции. Итак, каждый бит принимает одно значение: 1 или 0. Чтобы преобразовать число start в goal, необходимо инвертировать все различающиеся в одной и той же позиции биты, а совпадающие - оставить на месте. То есть минимальное кол-во инвертирований для преобразования исходного числа в целевое = кол-ву позиций (count), в которых биты двоичных представлений этих чисел различаются. Чтобы определить различающиеся позиции, применяем оператор XOR (исключающее ИЛИ), сравнивающий два бита: - если биты одинаковые -> 0 - если биты разные -> 1 start ^ goal даёт значение, в котором единицы стоят в тех позициях, где биты различаются. Теперь посчитаем кол-во единиц в значении xor, используя побитовый И: - только если оба бита равны 1 -> 1 - иначе -> 0 Пока xor больше 0 (есть хотя бы одна единица): - xor & (xor - 1): При (xor - 1) получаем новое число, в котором самая правая единица инвертируется в ноль, все нули справа от неё - в единицы, а биты слева - не изменяются. Затем при операции побитового И(&) между этим новым значением и исходным числом: Биты слева не меняются, так как одинаковы в обоих числах; Самая правая единица обнуляется; Все биты справа остаются нулями. Таким образом, удаляется ровно одна правая единица. - на каждой итерации увеличиваем count (кол-во единиц в xor) на 1. Возвращаем count, хранящее кол-во единиц в xor, а значит, минимальное кол-во инвертирований битов. Сложность O(k) - по времени (где k - кол-во единиц в xor) O(1) - по памяти (храним переменные count и xor) Код class Solution: def minBitFlips(self, start: int, goal: int) -> int: count = 0 xor = start ^ goal while xor: xor = xor & (xor - 1) count += 1 return count @algoses