Перестановка битов через OR и XOR

Средняя

Даны две двоичные строки одинаковой длины: start и goal. Со строкой start можно сколько угодно раз делать такую операцию: - выбрать два разных индекса i и j; - одновременно заменить start[i] на start[i] OR start[j], а start[j] — на start[i] XOR start[j] (в обеих формулах берутся старые значения). Например, из "0110" при i = 0, j = 2 получается "1110". Верните True, если такими операциями можно превратить start в goal, и False иначе.

Пример 1

start="001", goal="110" → True

i = 0, j = 2: «001» → «101». Затем i = 1, j = 2: «101» → «111». Наконец i = 0, j = 2: 1 OR 1 = 1 и 1 XOR 1 = 0, получаем «110».

Пример 2

start="000", goal="010" → False

Из нулей операции получают только нули: 0 OR 0 = 0 и 0 XOR 0 = 0. Единицу взять неоткуда.

Пример 3

start="10", goal="00" → False

Если хоть одна единица есть, её не уничтожить: при паре (1, x) на месте i всегда остаётся 1 OR x = 1, а при паре (0, 1) на месте i появляется 1.

Ограничения

2 ≤ len(start) ≤ 10⁵
len(goal) == len(start)
Обе строки состоят только из символов 0 и 1

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Bit Manipulation String

Вход

start="001", goal="110"

Ожидается

True

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 98 тестов на сервере, включая скрытые.