Преобразуйте данную двоичную строку в другую с минимальными операциями, перевернув все биты, кроме любого 1

Опубликовано: 20 Сентября, 2022

Имея две бинарные строки s1 и s2 , задача состоит в том, чтобы подсчитать минимальное количество операций для преобразования строки s1 в s2 . В одной операции может быть выбран установленный бит, а все остальные биты, кроме этого, перевернуты. Если невозможно преобразовать s1-> s2, выведите -1 .

Примеры:

Input: s1 = “100010111”   s2 = “101101100”
Output: 3
Explanation: 
In the first operation hold 1 at 6 th index and convert remaining to logical NOT: 100010111→011101100 .
In the second operation hold 1 at 1st index  and convert remaining to logical NOT: 011101100→110010011.
In the third operation hold 1 at 0th index and convert remaining to logical NOT: 110010011→101101100.
So 3 operations.

Input: s1=”11111″  s2 = “00000”
Output: -1

Подход: видно, что при выборе того же индекса 1 после двух операций строка остается такой же, как и исходная. Таким образом, для каждой операции следует выбирать разные индексы, чтобы «10» в строке s1 можно было преобразовать в строку «01» в строке s2 двумя операциями. Таким образом, ответ зависит от минимизации количества «10» и «01» в строках s1 и s2. Если по какому-либо индексу «0(s1) – 1(s2)» && «1(s1) – 0(s2)» равны по количеству, то есть ответ еще -1.

“01” (on choosing 1 at index1) -> “11”(on choosing 1 at index2)  -> “10”

Using this conclusion: 
It can be even possible that minimum “0(s1) – 1(s2) ” && “1(s1) – 0(s2)”  pairs can be obtained by doing 1 operation initially. In the cases where 1 (s1)-> 1(s2) or 1(s1) -> 0(s2).

Выполните следующие действия, чтобы решить эту проблему:

  • Инициализировать переменную res = INT_MAX
  • Инициализируйте переменную ops1=-1 для хранения операций, необходимых для преобразования строки s1 в s2 без каких-либо изменений.
  • Теперь проверьте, можно ли минимизировать операции, выполнив 1 начальную модификацию в случае (1(s1)-> 1(s2)) .
  • Сохраните операции в переменной ops2 и сохраните минимум в res , выполнив min(res,ops2) .
  • Теперь проверьте, можно ли минимизировать операции, выполнив 1 начальную модификацию в случае (1(s1)-> 0(s2)) .
  • Сохраните операции в переменной ops3 и сохраните минимум в res , выполнив min(res,ops3) .
  • Если res равно INT_MAX , это означает, что невозможно преобразовать строку s1 -> s2, поэтому выведите -1.
  • В противном случае распечатайте res .

Ниже приведена реализация вышеуказанного подхода:


Временная сложность: O(N), где N — длина строки.
Космическая сложность: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ