Dadas dos strings binarias A y B , la tarea es convertir A en B eligiendo cualquier substring de A y negándola (reemplazar cada 0 con 1 y cada 1 con 0). Imprime el número mínimo de operaciones requeridas.
Ejemplos:
Entrada: A = «101010», B = «110011»
Salida: 2
Elija la substring de longitud 2 del índice 1 a 2 y niéguela, luego A se convierte en «110010» y luego tome el último carácter y niéguelo.
La string final se convierte en «110011»
Entrada: A = «1010101», B = «0011100»
Salida: 3
Enfoque: cree una array en blanco y marque los índices que deben negarse. Luego, la respuesta será el número de bloques de 1 consecutivos en la array, ya que un solo bloque se puede negar en una sola operación.
Por ejemplo, A = “101010” y B = “110011”
La array recién creada será {0, 1, 1, 0, 0, 1} por lo que la respuesta será 2,
A después de la primera operación será “110010”
Después segunda operación «110011»
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <iostream>
using namespace std;
// Function to find the minimum steps
// to convert string a to string b
void convert(int n, string a, string b)
{
// array to mark the positions
// needed to be negated
int l[n];
int i;
for (i = 0; i < n; i++)
l[i] = 0;
for (i = 0; i < n; i++) {
// If two character are not same
// then they need to be negated
if (a[i] != b[i])
l[i] = 1;
}
// To count the blocks of 1
int cc = 0;
// To count the number of 1's in
// each block of 1's
int vl = 0;
for (i = 0; i < n; i++) {
if (l[i] == 0) {
if (vl != 0)
cc += 1;
vl = 0;
}
else
vl += 1;
}
// For the last block of 1's
if (vl != 0)
cc += 1;
cout << cc << endl;
}
// Driver code
int main()
{
string a = "101010";
string b = "110011";
int n = a.length();
convert(n, a, b);
return 0;
}
// This code is contributed by ANKITRAI1
Java
// Java implementation of the above approach
import java.util.*;
class solution {
// Function to find the minimum steps
// to convert string a to string b
static void convert(int n, String a, String b)
{
// array to mark the positions
// needed to be negated
int[] l = new int[n];
int i;
for (i = 0; i < n; i++)
l[i] = 0;
for (i = 0; i < n; i++) {
// If two character are not same
// then they need to be negated
if (a.charAt(i) != b.charAt(i))
l[i] = 1;
}
// To count the blocks of 1
int cc = 0;
// To count the number of 1's in
// each block of 1's
int vl = 0;
for (i = 0; i < n; i++) {
if (l[i] == 0) {
if (vl != 0)
cc += 1;
vl = 0;
}
else
vl += 1;
}
// For the last block of 1's
if (vl != 0)
cc += 1;
System.out.println(cc);
}
// Driver code
public static void main(String args[])
{
String a = "101010";
String b = "110011";
int n = a.length();
convert(n, a, b);
}
}
Python3
# Python3 implementation of the above approach # Function to find the minimum steps # to convert string a to string b def convert(n, a, b): # List to mark the positions needed to # be negated l = [0] * n for i in range(n): # If two character are not same # then they need to be negated if(a[i] != b[i]): l[i] = 1 # To count the blocks of 1 cc = 0 # To count the number of 1's in each # block of 1's vl = 0 for i in range(n): if (l[i] == 0): if(vl != 0): cc += 1 vl = 0 else: vl += 1 # For the last block of 1's if(vl != 0): cc += 1 print(cc) # Driver code a = "101010" b = "110011" n = len(a) convert(n, a, b)
C#
// C# implementation of the above approach
using System;
class GFG {
// Function to find the minimum steps
// to convert string a to string b
static void convert(int n, String a, String b)
{
// array to mark the positions
// needed to be negated
int[] l = new int[n];
int i;
for (i = 0; i < n; i++)
l[i] = 0;
for (i = 0; i < n; i++) {
// If two character are not same
// then they need to be negated
if (a[i] != b[i])
l[i] = 1;
}
// To count the blocks of 1
int cc = 0;
// To count the number of 1's in
// each block of 1's
int vl = 0;
for (i = 0; i < n; i++) {
if (l[i] == 0) {
if (vl != 0)
cc += 1;
vl = 0;
}
else
vl += 1;
}
// For the last block of 1's
if (vl != 0)
cc += 1;
Console.WriteLine(cc);
}
// Driver code
static public void Main()
{
String a = "101010";
String b = "110011";
int n = a.Length;
convert(n, a, b);
}
}
// This code is contributed by jit_t.
PHP
<?php
// PHP implementation of the above approach
// Function to find the minimum steps
// to convert string a to string b
function convert($n, $a, $b)
{
// array to mark the positions
// needed to be negated
$l = array_fill(0, $n, NULL);
for ($i = 0; $i < $n; $i++)
$l[$i] = 0 ;
for($i = 0; $i < $n; $i++)
{
// If two character are not same
// then they need to be negated
if($a[$i] != $b[$i])
$l[$i] = 1 ;
}
// To count the blocks of 1
$cc = 0;
// To count the number of 1's in
// each block of 1's
$vl = 0 ;
for($i = 0; $i < $n ; $i++)
{
if ($l[$i] == 0)
{
if($vl != 0)
$cc += 1 ;
$vl = 0 ;
}
else
$vl += 1 ;
}
// For the last block of 1's
if($vl != 0)
$cc += 1 ;
echo $cc . "\n";
}
// Driver code
$a = "101010";
$b = "110011";
$n = strlen($a);
convert($n, $a, $b) ;
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript implementation of
// the above approach
// Function to find the minimum steps
// to convert string a to string b
function convert(n, a, b)
{
// array to mark the positions
// needed to be negated
let l = new Array(n);
let i;
for (i = 0; i < n; i++)
l[i] = 0;
for (i = 0; i < n; i++) {
// If two character are not same
// then they need to be negated
if (a[i] != b[i])
l[i] = 1;
}
// To count the blocks of 1
let cc = 0;
// To count the number of 1's in
// each block of 1's
let vl = 0;
for (i = 0; i < n; i++) {
if (l[i] == 0) {
if (vl != 0)
cc += 1;
vl = 0;
}
else
vl += 1;
}
// For the last block of 1's
if (vl != 0)
cc += 1;
document.write(cc + "</br>");
}
let a = "101010";
let b = "110011";
let n = a.length;
convert(n, a, b);
</script>
Producción:
2