Dadas dos strings binarias A y B de longitud N , la tarea es verificar si la string A se puede convertir en B invirtiendo las substrings de A que contienen un número par de 1 s.
Ejemplos:
Entrada: A = “10011”, B = “11100”
Salida: Sí
Explicación: Substring inversa A[2, 5], 1 0011 → 11100.
Después de completar los pasos anteriores, las strings A y B son iguales.Entrada: A = “10011” B = “00111”
Salida: No
Enfoque: La idea se basa en las siguientes observaciones:
- Si la string A se puede transformar en la string B , entonces lo contrario también es válido, ya que las operaciones para convertir A en B se pueden invertir para convertir B en A.
- A solo puede hacerse igual a B cuando:
- Longitud (A) = Longitud (B) y el número de 1 en A y B es el mismo, y
- cnt A = cnt B donde cnt S es el número de Posición i donde 1 ≤ i ≤ longitud(S) y (∑ i j=1 (S j ))mod 2 = 1 .
Siga los pasos a continuación para resolver el problema:
- Atraviese la string A y B y almacene la frecuencia de 1 en variables, digamos count1A y count1B respectivamente.
- Inicialice una variable, digamos temp , para almacenar el conteo temporal de 1s .
- Recorra la string A usando la variable i y realice los siguientes pasos:
- Si el carácter actual es 1 , aumente la temperatura en 1 .
- De lo contrario, si el valor de temp es impar , incremente la variable odd1A en 1 . De lo contrario, incremente la variable even1A en 1.
- Repita los pasos anteriores 2 a 3 para la string B también.
- Después de completar los pasos anteriores, si el valor de conteo1A y conteo1B es el mismo, el valor de impar1A y impar1B es el mismo, y el valor de par1A y par1B es el mismo, entonces imprima «Sí»; de lo contrario, imprima «No» .
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 check if string A can be
// transformed to string B by reversing
// substrings of A having even number of 1s
void canTransformStrings(string A, string B)
{
// Store the size of string A
int n1 = A.size();
// Store the size of string B
int n2 = B.size();
// Store the count of 1s in A and B
int count1A = 0, count1B = 0;
// Stores cntA for string A
// and cntB for string B
int odd1A = 0, odd1B = 0;
int even1A = 0, even1B = 0;
// Traverse the string A
for (int i = 0; i < n1; i++) {
// If current character is 1
if (A[i] == '1')
// Increment 1s count
count1A++;
// Otherwise, update odd1A or
// even1A depending whether
// count1A is odd or even
else {
if (count1A & 1)
odd1A++;
else
even1A++;
}
}
// Traverse the string B
for (int i = 0; i < n2; i++) {
// If current character is 1
if (B[i] == '1')
// Increment 1s count
count1B++;
// Otherwise, update odd1B or
// even1B depending whether
// count1B is odd or even
else {
if (count1B & 1)
odd1B++;
else
even1B++;
}
}
// If the condition is satisfied
if (count1A == count1B
&& odd1A == odd1B
&& even1A == even1B) {
// If true, print Yes
cout << "Yes";
}
// Otherwise, print No
else
cout << "No";
}
// Driver Code
int main()
{
string A = "10011", B = "11100";
// Function Call
canTransformStrings(A, B);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to check if string A can be
// transformed to string B by reversing
// substrings of A having even number of 1s
public static void canTransformStrings(String A,
String B)
{
// Store the size of string A
int n1 = A.length();
// Store the size of string B
int n2 = B.length();
// Store the count of 1s in A and B
int count1A = 0, count1B = 0;
// Stores cntA for string A
// and cntB for string B
int odd1A = 0, odd1B = 0;
int even1A = 0, even1B = 0;
// Traverse the string A
for(int i = 0; i < n1; i++)
{
// If current character is 1
if (A.charAt(i) == '1')
// Increment 1s count
count1A++;
// Otherwise, update odd1A or
// even1A depending whether
// count1A is odd or even
else
{
if ((count1A & 1) == 1)
odd1A++;
else
even1A++;
}
}
// Traverse the string B
for(int i = 0; i < n2; i++)
{
// If current character is 1
if (B.charAt(i) == '1')
// Increment 1s count
count1B++;
// Otherwise, update odd1B or
// even1B depending whether
// count1B is odd or even
else
{
if ((count1B & 1) == 1)
odd1B++;
else
even1B++;
}
}
// If the condition is satisfied
if (count1A == count1B &&
odd1A == odd1B &&
even1A == even1B)
{
// If true, print Yes
System.out.print("Yes");
}
// Otherwise, print No
else
System.out.print("No");
}
// Driver Code
public static void main(String[] args)
{
String A = "10011", B = "11100";
// Function Call
canTransformStrings(A, B);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python program for the above approach
# Function to check if string A can be
# transformed to string B by reversing
# substrings of A having even number of 1s
def canTransformStrings(A, B):
# Store the size of string A
n1 = len(A);
# Store the size of string B
n2 = len(B);
# Store the count of 1s in A and B
count1A = 0;
count1B = 0;
# Stores cntA for string A
# and cntB for string B
odd1A = 0; odd1B = 0;
even1A = 0; even1B = 0;
# Traverse the string A
for i in range(n1):
# If current character is 1
if (A[i] == '1'):
# Increment 1s count
count1A += 1;
# Otherwise, update odd1A or
# even1A depending whether
# count1A is odd or even
else:
if ((count1A & 1) == 1):
odd1A += 1;
else:
even1A += 1;
# Traverse the string B
for i in range(n2):
# If current character is 1
if (B[i] == '1'):
# Increment 1s count
count1B += 1;
# Otherwise, update odd1B or
# even1B depending whether
# count1B is odd or even
else:
if ((count1B & 1) == 1):
odd1B += 1;
else:
even1B += 1;
# If the condition is satisfied
if (count1A == count1B and odd1A == odd1B and even1A == even1B):
# If True, print Yes
print("Yes");
# Otherwise, print No
else:
print("No");
# Driver Code
if __name__ == '__main__':
A = "10011";
B = "11100";
# Function Call
canTransformStrings(A, B);
# This code is contributed by Princi Singh
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG {
// Function to check if string A can be
// transformed to string B by reversing
// substrings of A having even number of 1s
static void canTransformStrings(string A, string B)
{
// Store the size of string A
int n1 = A.Length;
// Store the size of string B
int n2 = B.Length;
// Store the count of 1s in A and B
int count1A = 0, count1B = 0;
// Stores cntA for string A
// and cntB for string B
int odd1A = 0, odd1B = 0;
int even1A = 0, even1B = 0;
// Traverse the string A
for(int i = 0; i < n1; i++)
{
// If current character is 1
if (A[i] == '1')
// Increment 1s count
count1A++;
// Otherwise, update odd1A or
// even1A depending whether
// count1A is odd or even
else
{
if ((count1A & 1) == 1)
odd1A++;
else
even1A++;
}
}
// Traverse the string B
for(int i = 0; i < n2; i++)
{
// If current character is 1
if (B[i] == '1')
// Increment 1s count
count1B++;
// Otherwise, update odd1B or
// even1B depending whether
// count1B is odd or even
else
{
if ((count1B & 1) == 1)
odd1B++;
else
even1B++;
}
}
// If the condition is satisfied
if (count1A == count1B &&
odd1A == odd1B &&
even1A == even1B)
{
// If true, print Yes
Console.Write("Yes");
}
// Otherwise, print No
else
Console.Write("No");
}
static void Main()
{
string A = "10011", B = "11100";
// Function Call
canTransformStrings(A, B);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// JavaScript program for above approach
// Function to check if string A can be
// transformed to string B by reversing
// substrings of A having even number of 1s
function canTransformStrings(A, B)
{
// Store the size of string A
let n1 = A.length;
// Store the size of string B
let n2 = B.length;
// Store the count of 1s in A and B
let count1A = 0, count1B = 0;
// Stores cntA for string A
// and cntB for string B
let odd1A = 0, odd1B = 0;
let even1A = 0, even1B = 0;
// Traverse the string A
for(let i = 0; i < n1; i++)
{
// If current character is 1
if (A[i] == '1')
// Increment 1s count
count1A++;
// Otherwise, update odd1A or
// even1A depending whether
// count1A is odd or even
else
{
if ((count1A & 1) == 1)
odd1A++;
else
even1A++;
}
}
// Traverse the string B
for(let i = 0; i < n2; i++)
{
// If current character is 1
if (B[i] == '1')
// Increment 1s count
count1B++;
// Otherwise, update odd1B or
// even1B depending whether
// count1B is odd or even
else
{
if ((count1B & 1) == 1)
odd1B++;
else
even1B++;
}
}
// If the condition is satisfied
if (count1A == count1B &&
odd1A == odd1B &&
even1A == even1B)
{
// If true, print Yes
document.write("Yes");
}
// Otherwise, print No
else
document.write("No");
}
// Driver Code
let A = "10011", B = "11100";
// Function Call
canTransformStrings(A, B);
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)