Сложность: medium
Даны три положительных числа a, b и c. Верните минимальное количество переворотов, необходимых в некоторых битах a и b, чтобы сделать (a OR b == c) (побитовая операция OR). Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или с 0 на 1 в их двоичном представлении.
Пример:
Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)
👨💻 Алгоритм:
1⃣Инициализируйте переменную answer как 0, которая будет использоваться для отслеживания минимального количества необходимых переворотов.
2⃣Итеративно обрабатывайте каждый бит двоичного представления чисел a, b и c одновременно:
Если (c & 1) == 0, обновите answer как answer += (a & 1) + (b & 1).
Если (c & 1) == 1, и если оба значения a & 1 и b & 1 равны 0, увеличьте answer на 1.
3⃣Сдвигайте все числа вправо с помощью a >>= 1, b >>= 1, c >>= 1. Если все числа равны 0, верните answer, в противном случае, повторите шаги 2 и 3.
😎 Решение:
class Solution:
def minFlips(self, a: int, b: int, c: int) -> int:
answer = 0
while a != 0 or b != 0 or c != 0:
if (c & 1) == 1:
if (a & 1) == 0 and (b & 1) == 0:
answer += 1
else:
answer += (a & 1) + (b & 1)
a >>= 1
b >>= 1
c >>= 1
return answer
Ставь 👍 и забирай 📚 Базу знаний