Dadas dos strings binarias A y B de longitud N, la tarea es convertir la string de A a la string B cambiando repetidamente todos los bits de un prefijo de A , es decir, convertir todos los 0 del prefijo en 1 y viceversa. viceversa e imprima el número mínimo de cambios de prefijo necesarios y la longitud de los prefijos respectivos.
Ejemplos:
Entrada: A = “001”, B = “000”
Salida:
2
3 2
Explicación:
Cambiar el prefijo “001” modifica la string a “110”.
Voltear el prefijo «11» modifica la string a «000».Entrada: A = “1000”, B = “1011”
Salida:
2
4 2
Explicación:
Cambiar el prefijo “1000” modifica la string a “0111”.
Voltear el prefijo «01» modifica la string a «1011».
Enfoque ingenuo: El enfoque más simple es atravesar la string A en sentido inverso y por cada i -ésimo carácter obtenido de tal forma que A[i] no sea igual a B[i] , voltear los caracteres presentes en A de los índices [0, i] y incrementar el número de operaciones en 1 . Después de completar el recorrido de la string, imprima el recuento de operaciones y la longitud del prefijo elegido en cada operación.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea es arreglar un bit a la vez recorriendo la string A en sentido inverso. Mantenga una variable booleana, digamos invertir , inicialmente establecida en falso , para indicar si los bits actuales en A están invertidos o no. Mientras se desplaza, realice lo siguiente:
- Si el bit iᵗʰ en A no es igual al bit iᵗʰ en B e invert es falso , entonces incremente el conteo de operaciones y establezca invert en verdadero .
- De lo contrario, si el bit iᵗʰ en A es igual al bit iᵗʰ en B e invert es verdadero , entonces incremente el conteo de operaciones y establezca invertir en falso .
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable booleana, digamos invertir como falso, para indicar si los bits en A están invertidos o no.
- Inicialice una array vacía , digamos res, para almacenar la longitud del prefijo en cada operación.
- Iterar en el rango [N – 1, 0] usando la variable i y realizar los siguientes pasos:
- Si A[i] != B[i] e invert es false , entonces se requiere invertir el bit actual. Por lo tanto. inserte (i + 1) en la array res y actualice invert a true .
- De lo contrario, verifique si A[i] == B[i] e invert es true , luego inserte (i + 1) en res y actualice invert a false .
- Imprime el tamaño de la array res como el número de operaciones requeridas para hacer que las dos strings sean iguales.
- Luego, imprima los valores almacenados en res para indicar la longitud del prefijo en cada operación.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count flips required // to make strings A and B equal void findOperations(string A, string B, int N) { // Stores the count of the // number of operations int operations = 0; // Stores the length of // the chosen prefixes vector<int> ops; // Stores if operations are // performed even or odd times bool invert = false; // Traverse the given string for (int i = N - 1; i >= 0; i--) { // If current characters in // the two strings are unequal if (A[i] != B[i]) { // If A[i] is not flipped if (!invert) { // Increment count // of operations operations++; // Insert the length of // the chosen prefix ops.push_back(i + 1); // Update invert to true invert = true; } } else { // If A[i] is flipped if (invert) { // Increment count // of operations operations++; // Insert length of // the chosen prefix ops.push_back(i + 1); // Update invert to false invert = false; } } } // Print the number of // operations required cout << operations << endl; // Print the chosen prefix // length in each operation if (operations != 0) { for (auto x : ops) cout << x << " "; } } // Driver Code int main() { // Given binary strings string A = "001", B = "000"; int N = A.size(); findOperations(A, B, N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to count flips required // to make Strings A and B equal static void findOperations(String A, String B, int N) { // Stores the count of the // number of operations int operations = 0; // Stores the length of // the chosen prefixes Vector<Integer> ops = new Vector<>(); // Stores if operations are // performed even or odd times boolean invert = false; // Traverse the given String for (int i = N - 1; i >= 0; i--) { // If current characters in // the two Strings are unequal if (A.charAt(i) != B.charAt(i)) { // If A[i] is not flipped if (!invert) { // Increment count // of operations operations++; // Insert the length of // the chosen prefix ops.add(i + 1); // Update invert to true invert = true; } } else { // If A[i] is flipped if (invert) { // Increment count // of operations operations++; // Insert length of // the chosen prefix ops.add(i + 1); // Update invert to false invert = false; } } } // Print the number of // operations required System.out.print(operations +"\n"); // Print the chosen prefix // length in each operation if (operations != 0) { for (int x : ops) System.out.print(x+ " "); } } // Driver Code public static void main(String[] args) { // Given binary Strings String A = "001", B = "000"; int N = A.length(); findOperations(A, B, N); } } // This code is contributed by Amit Katiyar
Python3
# Python program for the above approach # Function to count flips required # to make strings A and B equal def findOperations(A, B, N): # Stores the count of the # number of operations operations = 0 # Stores the length of # the chosen prefixes ops = [] # Stores if operations are # performed even or odd times invert = False # Traverse the given string for i in range(N - 1, -1, -1): # If current characters in # the two strings are unequal if (A[i] != B[i]): # If A[i] is not flipped if (not invert): # Increment count # of operations operations += 1 # Insert the length of # the chosen prefix ops.append(i + 1) # Update invert to true invert = True else: # If A[i] is flipped if (invert): # Increment count # of operations operations += 1 # Insert length of # the chosen prefix ops.append(i + 1) # Update invert to false invert = False # Print the number of # operations required print (operations) # Print the chosen prefix # length in each operation if (operations != 0): for x in ops: print(x, end = " ") # Driver Code if __name__ == '__main__': # Given binary strings A, B = "001", "000" N = len(A) findOperations(A, B, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to count flips required // to make Strings A and B equal static void findOperations(String A, String B, int N) { // Stores the count of the // number of operations int operations = 0; // Stores the length of // the chosen prefixes List<int> ops = new List<int>(); // Stores if operations are // performed even or odd times bool invert = false; // Traverse the given String for(int i = N - 1; i >= 0; i--) { // If current characters in // the two Strings are unequal if (A[i] != B[i]) { // If A[i] is not flipped if (!invert) { // Increment count // of operations operations++; // Insert the length of // the chosen prefix ops.Add(i + 1); // Update invert to true invert = true; } } else { // If A[i] is flipped if (invert) { // Increment count // of operations operations++; // Insert length of // the chosen prefix ops.Add(i + 1); // Update invert to false invert = false; } } } // Print the number of // operations required Console.Write(operations + "\n"); // Print the chosen prefix // length in each operation if (operations != 0) { foreach(int x in ops) Console.Write(x + " "); } } // Driver Code public static void Main(String[] args) { // Given binary Strings String A = "001", B = "000"; int N = A.Length; findOperations(A, B, N); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript program for the above approach // Function to count flips required // to make Strings A and B equal function findOperations(A, B, N) { // Stores the count of the // number of operations var operations = 0; // Stores the length of // the chosen prefixes var ops = []; // Stores if operations are // performed even or odd times var invert = false; // Traverse the given String for (var i = N - 1; i >= 0; i--) { // If current characters in // the two Strings are unequal if (A[i] !== B[i]) { // If A[i] is not flipped if (!invert) { // Increment count // of operations operations++; // Insert the length of // the chosen prefix ops.push(i + 1); // Update invert to true invert = true; } } else { // If A[i] is flipped if (invert) { // Increment count // of operations operations++; // Insert length of // the chosen prefix ops.push(i + 1); // Update invert to false invert = false; } } } // Print the number of // operations required document.write(operations + "<br>"); // Print the chosen prefix // length in each operation if (operations !== 0) { for (const x of ops) { document.write(x + " "); } } } // Driver Code // Given binary Strings var A = "001", B = "000"; var N = A.length; findOperations(A, B, N); </script>
2 3 2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por pawanharwani11 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA