Convierta una string binaria en otra cambiando los prefijos un número mínimo de veces

Dadas dos strings binarias A y B de longitud N , la tarea es convertir la string A en B cambiando repetidamente un prefijo de A , invirtiendo el orden de aparición de los bits en el prefijo elegido. Imprime el número de vueltas requeridas y la longitud de todos los prefijos.

Ejemplos:

Entrada: A = “01”, B = “10”
Salida:
3
1 2 1
Explicación:
Operación 1: Seleccione el prefijo de longitud 1 de la string A (= “01”). Voltear el prefijo «0» modifica la string a «11».
Operación 2: Seleccione el prefijo de longitud 2 de la string A (= “11”). Voltear el prefijo «11» modifica la string a «00».
Operación 3: Seleccione el prefijo de longitud 1 de la string A (= “00”). Cambiar el prefijo «0» a «1» modifica la string a «10», que es lo mismo que la string B.
Por lo tanto, el número total de operaciones requeridas es 3.

Entrada:  A = “0”, B = “1”
Salida:
1
1

Enfoque: el problema dado se puede resolver arreglando los bits uno por uno. Para corregir el i ^-ésimo bit , cuando A[i] y  B[i] no son iguales, invierta el prefijo de longitud i y luego invierta el prefijo de longitud 1 . Ahora, voltea el prefijo de longitud i . Estas tres operaciones no cambian ningún otro bit en A. Realice estas operaciones en todos los índices donde A[i] es diferente de B[i]. Dado que se usan 3 operaciones por bit, se usarán 3 * N operaciones en total. 

Para minimizar el número de operaciones, el enfoque anterior puede modificarse fijando los bits uno por uno en orden inverso. Para corregir el i ^-ésimo bit , se requiere que se invierta el prefijo de longitud i o el primer bit, y luego se requiere que se invierta el prefijo de longitud i . Pero en orden inverso, los bits previamente fijados no se vuelven a invertir con este procedimiento y se necesitan como máximo 2 operaciones por bit. Por lo tanto, el número mínimo de operaciones requeridas es 2*N .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count minimum number
// of operations required to convert
// string a to another string b
void minOperations(string a, string b, int n)
{
    // Store the lengths of each
    // prefixes selected
    vector<int> ops;
 
    // Traverse the string
    for (int i = n - 1; i >= 0; i--) {
        if (a[i] != b[i]) {
 
            // If first character
            // is same as b[i]
            if (a[0] == b[i]) {
 
                // Insert 1 to ops[]
                ops.push_back(1);
 
                // And, flip the bit
                a[0] = '0' + !(a[0] - '0');
            }
 
            // Reverse the prefix
            // string of length i + 1
            reverse(a.begin(), a.begin() + i + 1);
 
            // Flip the characters
            // in this prefix length
            for (int j = 0; j <= i; j++) {
                a[j] = '0' + !(a[j] - '0');
            }
 
            // Push (i + 1) to array ops[]
            ops.push_back(i + 1);
        }
    }
 
    // Print the number of operations
    cout << ops.size() << "\n";
 
    // Print the length of
    // each prefixes stored
    for (int x : ops) {
        cout << x << ' ';
    }
}
 
// Driver Code
int main()
{
    string a = "10", b = "01";
    int N = a.size();
 
    minOperations(a, b, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG
{
 
  // Function to count minimum number
  // of operations required to convert
  // string a to another string b
  static void minOperations(String s1, String s2, int n)
  {
 
    char a[] = s1.toCharArray();
    char b[] = s2.toCharArray();
 
    // Store the lengths of each
    // prefixes selected
    ArrayList<Integer> ops = new ArrayList<>();
 
    // Traverse the string
    for (int i = n - 1; i >= 0; i--) {
      if (a[i] != b[i]) {
 
        // If first character
        // is same as b[i]
        if (a[0] == b[i]) {
 
          // Insert 1 to ops[]
          ops.add(1);
 
          // And, flip the bit
          a[0] = (a[0] == '0' ? '1' : '0');
        }
 
        // Reverse the prefix
        // string of length i + 1
        reverse(a, 0, i);
 
        // Flip the characters
        // in this prefix length
        for (int j = 0; j <= i; j++) {
          a[j] = (a[j] == '0' ? '1' : '0');
        }
 
        // Push (i + 1) to array ops[]
        ops.add(i + 1);
      }
    }
 
    // Print the number of operations
    System.out.println(ops.size());
 
    // Print the length of
    // each prefixes stored
    for (int x : ops) {
      System.out.print(x + " ");
    }
  }
 
  // Function to reverse a[]
  // from start to end
  static void reverse(char a[], int start, int end)
  {
 
    while (start < end) {
      char temp = a[start];
      a[start] = a[end];
      a[end] = temp;
      start++;
      end--;
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    String a = "10", b = "01";
    int N = a.length();
 
    minOperations(a, b, N);
  }
}
 
// This code is contributed by Kingash.

# Python 3  program for the above approach
 
# Function to count minimum number
# of operations required to convert
# string a to another string b
def minOperations(a,  b,  n):
 
    # Store the lengths of each
    # prefixes selected
    ops = []
    a = list(a)
 
    # Traverse the string
    for i in range(n - 1, -1, -1):
        if (a[i] != b[i]):
 
            # If first character
            # is same as b[i]
            if (a[0] == b[i]):
 
                # Insert 1 to ops[]
                ops.append(1)
 
                # And, flip the bit
                if(ord(a[0]) - ord('0')):
                    a[0] = chr(ord('0') + ord('0'))
                else:
                    a[0] = chr(ord('0') + ord('1'))
 
            # Reverse the prefix
            # string of length i + 1
 
            a[:i+1].reverse()
 
            # Flip the characters
            # in this prefix length
            for j in range(i+1):
                if(ord(a[j]) - ord('0')):
                    a[j] = chr(ord('0') + ord('0'))
                else:
                    a[j] = chr(ord('0') + ord('1'))
 
            # Push (i + 1) to array ops[]
            ops.append(i + 1)
 
    # Print the number of operations
    print(len(ops))
 
    # Print the length of
    # each prefixes stored
    for x in ops:
        print(x, end=" ")
 
# Driver Code
if __name__ == "__main__":
 
    a = "10"
    b = "01"
    N = len(a)
 
    minOperations(a, b, N)
 
    # This code is contributed by ukasp.

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
  // Function to count minimum number
  // of operations required to convert
  // string a to another string b
  static void minOperations(string s1, string s2, int n)
  {
 
    char[] a = s1.ToCharArray();
    char[] b = s2.ToCharArray();
 
    // Store the lengths of each
    // prefixes selected
    List<int> ops = new List<int>();
 
    // Traverse the string
    for (int i = n - 1; i >= 0; i--) {
      if (a[i] != b[i]) {
 
        // If first character
        // is same as b[i]
        if (a[0] == b[i]) {
 
          // Insert 1 to ops[]
          ops.Add(1);
 
          // And, flip the bit
          a[0] = (a[0] == '0' ? '1' : '0');
        }
 
        // Reverse the prefix
        // string of length i + 1
        reverse(a, 0, i);
 
        // Flip the characters
        // in this prefix length
        for (int j = 0; j <= i; j++) {
          a[j] = (a[j] == '0' ? '1' : '0');
        }
 
        // Push (i + 1) to array ops[]
        ops.Add(i + 1);
      }
    }
 
    // Print the number of operations
    Console.WriteLine(ops.Count);
 
    // Print the length of
    // each prefixes stored
    foreach (int x in ops) {
      Console.Write(x + " ");
    }
  }
 
  // Function to reverse a[]
  // from start to end
  static void reverse(char[] a, int start, int end)
  {
 
    while (start < end) {
      char temp = a[start];
      a[start] = a[end];
      a[end] = temp;
      start++;
      end--;
    }
  }
 
  // Driver Code
  public static void Main()
  {
    string a = "10", b = "01";
    int N = a.Length;
 
    minOperations(a, b, N);
  }
}
 
// This code is contributed by souravghosh0416.

<script>
      // JavaScript program to implement
      // the above approach
      // Function to count minimum number
      // of operations required to convert
      // string a to another string b
      function minOperations(s1, s2, n) {
        var a = s1.split("");
        var b = s2.split("");
 
        // Store the lengths of each
        // prefixes selected
        var ops = [];
 
        // Traverse the string
        for (var i = n - 1; i >= 0; i--) {
          if (a[i] !== b[i]) {
            // If first character
            // is same as b[i]
            if (a[0] === b[i]) {
              // Insert 1 to ops[]
              ops.push(1);
 
              // And, flip the bit
              a[0] = a[0] === "0" ? "1" : "0";
            }
 
            // Reverse the prefix
            // string of length i + 1
            reverse(a, 0, i);
 
            // Flip the characters
            // in this prefix length
            for (var j = 0; j <= i; j++) {
              a[j] = a[j] === "0" ? "1" : "0";
            }
 
            // Push (i + 1) to array ops[]
            ops.push(i + 1);
          }
        }
 
        // Print the number of operations
        document.write(ops.length + "<br>");
 
        // Print the length of
        // each prefixes stored
        for (const x of ops) {
          document.write(x + " ");
        }
      }
 
      // Function to reverse a[]
      // from start to end
      function reverse(a, start, end) {
        while (start < end) {
          var temp = a[start];
          a[start] = a[end];
          a[end] = temp;
          start++;
          end--;
        }
      }
 
      // Driver Code
      var a = "10", b = "01";
      var N = a.length;
 
      minOperations(a, b, N);
</script>

3
1 2 1

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)