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>
Producción:
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