Dadas dos strings binarias. La tarea es verificar si la string s1 se puede convertir en la string s2 realizando las operaciones dadas cualquier cantidad de veces.
- Elija dos caracteres adyacentes cualesquiera en una string s1 y reemplace uno de ellos por a^b y el otro por a
b (a OR b).
Ejemplos:
Entrada: S1 = “11”, S2 = “10”
Salida: SÍ
Seleccione dos caracteres adyacentes y reemplace s2[0] por s1[0]s1[1] y
cambie s2[1] por s1[0]^s1[1 ]
Entrada: S1 = “000”, S2 = “101”
Salida: NO
Enfoque: a continuación se incluye una tabla que explica todas las posibilidades de las operaciones XOR y OR.
| X | Y | X^Y | XY _ |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
Si la string consiste solo en 0 y su longitud es la misma, la conversión es posible, ya que dos ceros adyacentes darán como resultado solo ceros, independientemente de la operación realizada en él. Si ambas strings tienen 1, siga los pasos a continuación para verificar si String1 se puede convertir a String2.
- Comprobar si las longitudes son iguales o no
- Compruebe si ambas strings tienen un mínimo de 1, ya que todas las conversiones son posibles si ambas strings tienen al menos 1, que se puede ver en la tabla.
Si las dos condiciones anteriores son verdaderas, es posible convertir String1 en String2.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if string1 can be
// converted to string2 using XOR and OR operations
#include <bits/stdc++.h>
using namespace std;
// function to check if conversion is possible or not
bool solve(string s1, string s2)
{
bool flag1 = 0, flag2 = 0;
// if lengths are different
if (s1.length() != s2.length())
return false;
int l = s1.length();
// iterate to check if both strings have 1
for (int i = 0; i < l; i++) {
// to check if there is
// even one 1 in string s1
if (s1[i] == '1')
flag1 = 1;
// to check if there is even
// one 1 in string s2
if (s2[i] == '1')
flag2 = 1;
if (flag1 && flag2)
return true;
}
//if both strings have only '0'
if(!flag1&&!flag2)
return true;
// if both string do not have a '1'.
return false;
}
// Driver code
int main()
{
string s1 = "100101";
string s2 = "100000";
if (solve(s1, s2))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to check if
// string1 can be converted
// to string2 using XOR and
// OR operations
import java.io.*;
import java.util.*;
class GFG
{
// function to check if
// conversion is possible
// or not
static boolean solve(String s1,
String s2)
{
boolean flag1 = false,
flag2 = false;
// if lengths are different
if (s1.length() != s2.length())
return false;
int l = s1.length();
// iterate to check if
// both strings have 1
for (int i = 0; i < l; i++)
{
// to check if there is
// even one 1 in string s1
if (s1.charAt(i) == '1')
flag1 = true;
// to check if there is even
// one 1 in string s2
if (s2.charAt(i) == '1')
flag2 = true;
if (flag1 == true &&
flag2 == true)
return true;
}
//if both strings have only '0'
if(!flag1&&!flag2)
return true;
// if both string do
// not have a '1'.
return false;
}
// Driver code
public static void main(String args[])
{
String s1 = "100101";
String s2 = "100000";
if (solve(s1, s2) == true)
System.out.print("Yes");
else
System.out.print("No");
}
}
Python3
# Python3 program to check
# if string1 can be converted
# to string2 using XOR and
# OR operations
# function to check if
# conversion is possible or not
def solve(s1, s2):
flag1 = 0
flag2 = 0
# if lengths are different
if (len(s1) != len(s2)):
return False
l = len(s1)
# iterate to check if
# both strings have 1
for i in range (0, l):
# to check if there is
# even one 1 in string s1
if (s1[i] == '1'):
flag1 = 1;
# to check if there is even
# one 1 in string s2
if (s2[i] == '1'):
flag2 = 1
# if both string
# do not have a '1'.
if (flag1 & flag2):
return True
if(!flag1 & !flag2):
return True
return False
# Driver code
s1 = "100101"
s2 = "100000"
if solve(s1, s2):
print( "Yes")
else:
print("No")
# This code is contributed
# by Shivi_Aggarwal
C#
// C# program to check if
// string1 can be converted
// to string2 using XOR and
// OR operations
using System;
class GFG
{
// function to check if
// conversion is possible
// or not
static bool solve(String s1,
String s2)
{
bool flag1 = false,
flag2 = false;
// if lengths are different
if (s1.Length != s2.Length)
return false;
int l = s1.Length;
// iterate to check if
// both strings have 1
for (int i = 0; i < l; i++)
{
// to check if there is
// even one 1 in string s1
if (s1[i] == '1')
flag1 = true;
// to check if there is even
// one 1 in string s2
if (s2[i] == '1')
flag2 = true;
if (flag1 == true &&
flag2 == true)
return true;
}
//if both strings have only '0'
if(!flag1&&!flag2)
return true;
// if both string do
// not have a '1'.
return false;
}
// Driver code
public static void Main()
{
String s1 = "100101";
String s2 = "100000";
if (solve(s1, s2) == true)
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
// PHP program to check if string1
// can be converted to string2
// using XOR and OR operations
// function to check if conversion
// is possible or not
function solve($s1, $s2)
{
// if lengths are different
if (strlen($s1) != strlen($s2))
return false;
$l = strlen($s1);
// iterate to check if
// both strings have 1
for ($i = 0; $i < 1; $i++)
{
// to check if there is
// even one 1 in string s1
if ($s1[$i] == '1')
$flag1 = 1;
// to check if there is even
// one 1 in string s2
if ($s2[$i] == '1')
$flag2 = 1;
if (!$flag1 && !$flag2)
return true;
}
// if both string do
// not have a '1'.
return false;
}
// Driver code
$s1 = "100101";
$s2 = "100000";
if (solve($s1, $s2))
echo("Yes");
else
echo("No");
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript program to check if string1 can be
// converted to string2 using XOR and OR operations
// function to check if conversion is possible or not
function solve(s1, s2)
{
let flag1 = 0, flag2 = 0;
// if lengths are different
if (s1.length != s2.length)
return false;
let l = s1.length;
// iterate to check if both strings have 1
for (let i = 0; i < l; i++) {
// to check if there is
// even one 1 in string s1
if (s1[i] == '1')
flag1 = 1;
// to check if there is even
// one 1 in string s2
if (s2[i] == '1')
flag2 = 1;
if (flag1 && flag2)
return true;
}
//if both strings have only '0'
if(!flag1&&!flag2)
return true;
// if both string do not have a '1'.
return false;
}
// Driver code
let s1 = "100101";
let s2 = "100000";
if (solve(s1, s2))
document.write("Yes");
else
document.write("No");
</script>
Producción:
Yes
Complejidad de tiempo: O(n) donde n es la longitud de las strings de entrada.