Dadas dos strings binarias A y B , la tarea es encontrar el número mínimo de veces que una substring que comienza con el primer carácter de A debe invertirse, es decir, convertir 1 s en 0 s y 0 s en 1 s, para convertir A en B. _
Ejemplos:
Entrada: A = “0010”, B = “1011”
Salida; 3
Explicación:
Paso 1: Da la vuelta a toda la string A. Por lo tanto, A se convierte en “1101” .
Paso 2: cambia la substring {A[0], A[2]}. Por lo tanto, A se convierte en “0011”.
Paso 3: Voltear A[0]. Por lo tanto, A se convierte en «1011», que es igual a B.
Por lo tanto, el número mínimo de operaciones requeridas es 3.Entrada: A = “1010101”, B = “0011100”
Salida: 5
Explicación:
Paso 1: Voltee el entero. Por lo tanto, A se convierte en “0101010″
Paso 2: Voltee la substring {A[0], A[5]}. Por lo tanto, A se convierte en “1010100″
Paso 3: Cambia la substring {A[0], A[3]}. Por lo tanto, A se convierte en “0101100″
Paso 4: Cambia la substring {A[0], A[2]}. Por lo tanto, A se convierte en “1011100″
Paso 5: Voltear A[0]. Por lo tanto, A se convierte en «0011100», que es igual a B.
Por lo tanto, el número mínimo de operaciones requeridas es 5.
Enfoque: la idea es inicializar una variable que contiene el último índice en el que el carácter en A es diferente del carácter en B. Luego niega A desde el primer índice hasta el último índice. Repita hasta que ambas cuerdas se vuelvan iguales. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable last_index que contiene el último índice en el que los caracteres son diferentes en A y B .
- Niegue la string A desde el primer índice hasta el último_índice e incremente el conteo de pasos.
- Repita los pasos anteriores hasta que la string A sea igual a la string B.
- Imprima el recuento de pasos después de que ambas strings sean iguales después de realizar las operaciones.
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 that finds the minimum
// number of operations required such
// that string A and B are the same
void findMinimumOperations(string a,
string b)
{
// Stores the count of steps
int step = 0;
// Stores the last index whose
// bits are not same
int last_index;
// Iterate until both string
// are unequal
while (a != b) {
// Check till end of string to
// find rightmost unequals bit
for (int i = 0;
i < a.length(); i++) {
// Update the last index
if (a[i] != b[i]) {
last_index = i;
}
}
// Flipping characters up
// to the last index
for (int i = 0;
i <= last_index; i++) {
// Flip the bit
a[i] = (a[i] == '0') ? '1' : '0';
}
// Increasing steps by one
step++;
}
// Print the count of steps
cout << step;
}
// Driver Code
int main()
{
// Given strings A and B
string A = "101010", B = "110011";
// Function Call
findMinimumOperations(A, B);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Function that finds the minimum
// number of operations required such
// that String A and B are the same
static void findMinimumOperations(char[] a,
char[] b)
{
// Stores the count of steps
int step = 0;
// Stores the last index whose
// bits are not same
int last_index = 0;
// Iterate until both String
// are unequal
while (!Arrays.equals(a, b))
{
// Check till end of String to
// find rightmost unequals bit
for (int i = 0;
i < a.length; i++)
{
// Update the last index
if (a[i] != b[i])
{
last_index = i;
}
}
// Flipping characters up
// to the last index
for (int i = 0;
i <= last_index; i++)
{
// Flip the bit
a[i] = (a[i] == '0') ?
'1' : '0';
}
// Increasing steps by one
step++;
}
// Print the count of steps
System.out.print(step);
}
// Driver Code
public static void main(String[] args)
{
// Given Strings A and B
String A = "101010",
B = "110011";
// Function Call
findMinimumOperations(A.toCharArray(),
B.toCharArray());
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function that finds the minimum # number of operations required such # that string A and B are the same def findMinimumOperations(a, b): # Stores the count of steps step = 0 # Stores the last index whose # bits are not same last_index = 0 # Iterate until both string # are unequal while (a != b): a = [i for i in a] # Check till end of string to # find rightmost unequals bit for i in range(len(a)): # Update the last index if (a[i] != b[i]): last_index = i # Flipping characters up # to the last index for i in range(last_index + 1): # Flip the bit if (a[i] == '0'): a[i] = '1' else: a[i] = '0' a = "".join(a) # Increasing steps by one step += 1 # Print the count of steps print(step) # Driver Code if __name__ == '__main__': # Given strings A and B A = "101010" B = "110011" # Function Call findMinimumOperations(A, B) # This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
class GFG{
// Function that finds the minimum
// number of operations required such
// that string A and B are the same
static void findMinimumOperations(string a,
string b)
{
// Stores the count of steps
int step = 0;
// Stores the last index whose
// bits are not same
int last_index = 0;
// Iterate until both string
// are unequal
while (a.Equals(b) == false)
{
// Check till end of string to
// find rightmost unequals bit
for(int i = 0; i < a.Length; i++)
{
// Update the last index
if (a[i] != b[i])
{
last_index = i;
}
}
// Flipping characters up
// to the last index
char[] ch = a.ToCharArray();
for(int i = 0;
i <= last_index; i++)
{
// Flip the bit
if (ch[i] == '0')
{
ch[i] = '1';
}
else
{
ch[i] = '0';
}
}
a = new string(ch);
// Increasing steps by one
step++;
}
// Print the count of steps
Console.WriteLine(step);
}
// Driver Code
public static void Main()
{
// Given strings A and B
string A = "101010";
string B = "110011";
// Function Call
findMinimumOperations(A,B);
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// JavaScript program for the
// above approach
// Function that finds the minimum
// number of operations required such
// that string A and B are the same
function findMinimumOperations(a, b)
{
// Stores the count of steps
var step = 0;
// Stores the last index whose
// bits are not same
var last_index = 0;
// Iterate until both string
// are unequal
while (a !== b)
{
// Check till end of string to
// find rightmost unequals bit
for (var i = 0; i < a.length; i++)
{
// Update the last index
if (a[i] !== b[i])
{
last_index = i;
}
}
// Flipping characters up
// to the last index
var ch = a.split("");
for(var i = 0; i <= last_index; i++)
{
// Flip the bit
if (ch[i] === "0")
{
ch[i] = "1";
}
else
{
ch[i] = "0";
}
}
a = ch.join("");
// Increasing steps by one
step++;
}
// Print the count of steps
document.write(step);
}
// Driver Code
// Given strings A and B
var A = "101010";
var B = "110011";
// Function Call
findMinimumOperations(A, B);
// This code is contributed by rdtank
</script>
4
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por mohammaderfangooneh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA