Dadas dos strings binarias s1[] y s2[] de la misma longitud N, la tarea es encontrar el número mínimo de operaciones para que sean iguales. Imprime -1 si es imposible hacerlo. Una operación se define como elegir dos índices adyacentes de una de las strings binarias e invertir los caracteres en esas posiciones, es decir, 1 a 0 y viceversa.
Ejemplos:
Entrada: s1[] = “0101”, s2[] = “1111”
Salida: 2
Explicación: Invierta los caracteres en los índices 1 y 2 en la primera string y en los índices 0 y 1 en la segunda string para que sean iguales a 0011 Hay otras formas de hacerlo también como convertir a 1111, etc.Entrada: s1[] = “011”, s2[] = “111”
Salida: -1
Enfoque: la idea es atravesar linealmente ambas strings y, si en algún índice, los caracteres son diferentes, invierta el i -ésimo y (i+1) -ésimo carácter en la string s1[]. Siga los pasos a continuación para resolver el problema:
- Inicialice la variable count como 0 para almacenar la respuesta.
- Iterar sobre el rango [0, N] usando la variable i y realizar los siguientes pasos:
- Si s1[i] no es igual a s2[i] , realice las siguientes tareas:
- Si s1[i] es igual a 1, cámbielo a 0 , de lo contrario, cámbielo a 1.
- De manera similar, si s1[i+1] es igual a 1, cámbielo a 0 , de lo contrario, cámbielo a 1.
- Finalmente, aumente el valor de count en 1.
- Si s1[i] no es igual a s2[i] , realice las siguientes tareas:
- Si s1[] es igual a s2[], devuelve el valor de count como respuesta; de lo contrario, devuelve -1.
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 find the minimum number
// of inversions required.
int find_Min_Inversion(int n, string s1, string s2)
{
// Initializing the answer
int count = 0;
// Iterate over the range
for (int i = 0; i < n - 1; i++) {
if (s1[i] != s2[i]) {
// If s1[i]!=s2[i], then inverse
// the characters at i snd (i+1)
// positions in s1.
if (s1[i] == '1') {
s1[i] = '0';
}
else {
s1[i] = '1';
}
if (s1[i + 1] == '1') {
s1[i + 1] = '0';
}
else {
s1[i + 1] = '1';
}
// Adding 1 to counter
// if characters are not same
count++;
}
}
if (s1 == s2) {
return count;
}
return -1;
}
// Driver Code
int main()
{
int n = 4;
string s1 = "0101";
string s2 = "1111";
cout << find_Min_Inversion(n, s1, s2) << endl;
return 0;
}
C
// C program for the above approach
#include <stdio.h>
#include <string.h>
// Function to find the minimum number
// of inversions required.
int find_Min_Inversion(int n, char s1[1000], char s2[1000])
{
// Initializing the answer
int count = 0;
// Iterate over the range
for (int i = 0; i < n - 1; i++) {
if (s1[i] != s2[i]) {
// If s1[i]!=s2[i], then inverse
// the characters at i snd (i+1)
// positions in s1.
if (s1[i] == '1') {
s1[i] = '0';
}
else {
s1[i] = '1';
}
if (s1[i + 1] == '1') {
s1[i + 1] = '0';
}
else {
s1[i + 1] = '1';
}
// Adding 1 to counter
// if characters are not same
count++;
}
}
if (strcmp(s1, s2) != -1) {
return count;
}
return -1;
}
// Driver Code
int main()
{
int n = 4;
char s1[1000] = "0101";
char s2[1000] = "1111";
printf("%d\n", find_Min_Inversion(n, s1, s2));
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the minimum number
// of inversions required.
static int find_Min_Inversion(int n, char[] s1,
char[] s2)
{
// Initializing the answer
int count = 0;
// Iterate over the range
for (int i = 0; i < n - 1; i++) {
if (s1[i] != s2[i]) {
// If s1[i]!=s2[i], then inverse
// the characters at i snd (i+1)
// positions in s1.
if (s1[i] == '1') {
s1[i] = '0';
}
else {
s1[i] = '1';
}
if (s1[i + 1] == '1') {
s1[i + 1] = '0';
}
else {
s1[i + 1] = '1';
}
// Adding 1 to counter
// if characters are not same
count++;
}
}
if (String.copyValueOf(s1).equals(
String.copyValueOf(s2))) {
return count;
}
return -1;
}
// Driver Code
public static void main(String[] args)
{
int n = 4;
String s1 = "0101";
String s2 = "1111";
System.out.print(
find_Min_Inversion(n, s1.toCharArray(),
s2.toCharArray())
+ "\n");
}
}
// This code is contributed by umadevi9616
Python3
# Python 3 program for the above approach # Function to find the minimum number # of inversions required. def find_Min_Inversion(n, s1, s2): # Initializing the answer count = 0 # Iterate over the range s1 = list(s1) s2 = list(s2) for i in range(n - 1): if (s1[i] != s2[i]): # If s1[i]!=s2[i], then inverse # the characters at i snd (i+1) # positions in s1. if (s1[i] == '1'): s1[i] = '0' else: s1[i] = '1' if (s1[i + 1] == '1'): s1[i + 1] = '0' else: s1[i + 1] = '1' # Adding 1 to counter # if characters are not same count += 1 s1 = ''.join(s1) s2 = ''.join(s2) if (s1 == s2): return count return -1 # Driver Code if __name__ == '__main__': n = 4 s1 = "0101" s2 = "1111" print(find_Min_Inversion(n, s1, s2)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the minimum number
// of inversions required.
static int find_Min_Inversion(int n, char[] s1,
char[] s2)
{
// Initializing the answer
int count = 0;
// Iterate over the range
for (int i = 0; i < n - 1; i++) {
if (s1[i] != s2[i]) {
// If s1[i]!=s2[i], then inverse
// the characters at i snd (i+1)
// positions in s1.
if (s1[i] == '1') {
s1[i] = '0';
}
else {
s1[i] = '1';
}
if (s1[i + 1] == '1') {
s1[i + 1] = '0';
}
else {
s1[i + 1] = '1';
}
// Adding 1 to counter
// if characters are not same
count++;
}
}
if (new string(s1) == new string(s2)) {
return count;
}
return -1;
}
// Driver Code
public static void Main(string[] args)
{
int n = 4;
string s1 = "0101";
string s2 = "1111";
// Function call
Console.Write(find_Min_Inversion(n,
s1.ToCharArray(),
s2.ToCharArray())
+ "\n");
}
}
// This code is contributed by phasing17
Javascript
<script>
// Java program for the above approach
// Function to find the minimum number
// of inversions required.
function find_Min_Inversion(n, s1, s2)
{
// Initializing the answer
let count = 0;
// Iterate over the range
for (let i = 0; i < n - 1; i++) {
if (s1[i] != s2[i]) {
// If s1[i]!=s2[i], then inverse
// the characters at i snd (i+1)
// positions in s1.
if (s1[i] = '1') {
s1[i] = '0';
}
else {
s1[i] = '1';
}
if (s1[i + 1] = '1') {
s1[i + 1] = '0';
}
else {
s1[i + 1] = '1';
}
// Adding 1 to counter
// if characters are not same
count++;
}
}
if (s1 != s2) {
return count;
}
return -1;
}
// Driver Code
let n = 4;
let s1 = "0101";
let s2 = "1111";
document.write(find_Min_Inversion(n, s1, s2));
// This code is contributed by shivanisinghss2110
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por adarshsinghk y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA