Dadas dos strings binarias str1 y str2 que tienen la misma longitud, la tarea es encontrar si es posible igualar las dos strings binarias str1 y str2 intercambiando todos los 1 que ocurren en índices menores que el índice 0 s en la string binaria str1 .
Ejemplos:
Entrada: str1 = “0110”, str2 = “0011”
Salida: Posible
explicación:
Al intercambiar str1[2] con str1[3], la string binaria str1 se convierte en “0101”.
Al intercambiar str1[1] con str1[2], la string binaria str1 se convierte en “0011”.
La string binaria str1 se vuelve igual a la string binaria str2, por lo tanto, la salida requerida es Posible.Entrada: str1 = “101”, str2 = “010”
Salida: No es posible
Enfoque: La idea es contar el número de 1 y 0 en str1 y str2 y luego proceder en consecuencia. Siga los pasos a continuación para resolver el problema:
- Si el conteo de 1 s y 0 s no es igual en str1 y str2 , entonces la conversión no es posible.
- Atraviesa la cuerda .
- Comenzando desde el primer carácter, compare cada carácter uno por uno. Para cada carácter diferente en i , realice los siguientes pasos:
- Compruebe si el carácter actual de la string str1 es ‘0’ y curStr1Ones ( almacena el recuento actual de 1 de la string str1) es mayor que 0 . Si se determina que es cierto, cambie el carácter por ‘1’ y reduzca el valor de curStr1Ones en 1 .
- Compruebe si el carácter de la string str1 es ‘0’ y curStr1Ones es igual a 0 . Si se encuentra que es cierto, entonces incremente el valor de la bandera en 1 y rompa el bucle.
- Compruebe si el carácter de la string str1 es ‘1’ y el carácter de la string str2 es ‘0’ . Si se determina que es cierto, cambie el carácter de str1 por ‘0’ e incremente el valor de curStr1Ones en 1 .
- Finalmente, imprima «Posible» si la bandera es 0 , de lo contrario imprima «No posible».
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 it is possible to make
// two binary strings equal by given operations
void isBinaryStringsEqual(string str1, string str2)
{
// Stores count of 1's and 0's
// of the string str1
int str1Zeros = 0, str1Ones = 0;
// Stores count of 1's and 0's
// of the string str2
int str2Zeros = 0, str2Ones = 0;
int flag = 0;
// Stores current count of 1's
// present in the string str1
int curStr1Ones = 0;
// Count the number of 1's and 0's
// present in the strings str1 and str2
for (int i = 0; i < str1.length(); i++) {
if (str1[i] == '1') {
str1Ones++;
}
else if (str1[i] == '0') {
str1Zeros++;
}
if (str2[i] == '1') {
str2Ones++;
}
else if (str2[i] == '0') {
str2Zeros++;
}
}
// If the number of 1's and 0's
// are not same of the strings str1
// and str2 then print not possible
if (str1Zeros != str2Zeros && str1Ones != str2Ones) {
cout << "Not Possible";
}
else {
// Traversing through the
// strings str1 and str2
for (int i = 0; i < str1.length(); i++) {
// If the str1 character not
// equals to str2 character
if (str1[i] != str2[i]) {
// Swaps 0 with 1 of the
// string str1
if (str1[i] == '0' && curStr1Ones > 0) {
str1[i] = '1';
curStr1Ones--;
}
// Breaks the loop as the count
// of 1's is zero. Hence, no swaps possible
if (str1[i] == '0' && curStr1Ones == 0) {
flag++;
break;
}
// Swaps 1 with 0 in the string str1
if (str1[i] == '1' && str2[i] == '0') {
str1[i] = '0';
curStr1Ones++;
}
}
}
if (flag == 0) {
cout << "Possible";
}
// Print not possible
else {
cout << "Not Possible";
}
}
}
// Driver Code
int main()
{
// Given Strings
string str1 = "0110";
string str2 = "0011";
// Function Call
isBinaryStringsEqual(str1, str2);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to check if it is possible to make
// two binary strings equal by given operations
static void isBinaryStringsEqual(String str1,
String str2)
{
// Stores count of 1's and 0's
// of the string str1
int str1Zeros = 0, str1Ones = 0;
// Stores count of 1's and 0's
// of the string str2
int str2Zeros = 0, str2Ones = 0;
int flag = 0;
// Stores current count of 1's
// present in the string str1
int curStr1Ones = 0;
// Count the number of 1's and 0's
// present in the strings str1 and str2
for (int i = 0; i < str1.length(); i++)
{
if (str1.charAt(i) == '1')
{
str1Ones++;
}
else if (str1.charAt(i) == '0')
{
str1Zeros++;
}
if (str2.charAt(i) == '1')
{
str2Ones++;
}
else if (str2.charAt(i) == '0')
{
str2Zeros++;
}
}
// If the number of 1's and 0's
// are not same of the strings str1
// and str2 then print not possible
if (str1Zeros != str2Zeros
&& str1Ones != str2Ones)
{
System.out.println("Not Possible");
}
else {
// Traversing through the
// strings str1 and str2
for (int i = 0; i < str1.length(); i++)
{
// If the str1 character not
// equals to str2 character
if (str1.charAt(i) != str2.charAt(i))
{
// Swaps 0 with 1 of the
// string str1
if (str1.charAt(i) == '0'
&& curStr1Ones > 0)
{
str1 = str1.substring(0, i) + '1'
+ str1.substring(i + 1);
curStr1Ones--;
}
// Breaks the loop as the count
// of 1's is zero. Hence, no swaps
// possible
if (str1.charAt(i) == '0'
&& curStr1Ones == 0)
{
flag++;
break;
}
// Swaps 1 with 0 in the string str1
if (str1.charAt(i) == '1'
&& str2.charAt(i) == '0')
{
str1 = str1.substring(0, i) + '0'
+ str1.substring(i+1);
curStr1Ones++;
}
}
}
if (flag == 0) {
System.out.println("Possible");
}
// Print not possible
else {
System.out.println("Not Possible");
}
}
}
// Driver Code
public static void main(String[] args)
{
// Given Strings
String str1 = "0110";
String str2 = "0011";
// Function Call
isBinaryStringsEqual(str1, str2);
}
}
// This code is contributed by dharanendralv23
Python3
# Python program for the above approach
# Function to check if it is possible to make
# two binary strings equal by given operations
def isBinaryStringsEqual(list1, list2) :
str1 = list(list1)
str2 = list(list2)
# Stores count of 1's and 0's
# of the string str1
str1Zeros = 0
str1Ones = 0
# Stores count of 1's and 0's
# of the string str2
str2Zeros = 0
str2Ones = 0
flag = 0
# Stores current count of 1's
# present in the string str1
curStr1Ones = 0
# Count the number of 1's and 0's
# present in the strings str1 and str2
for i in range(len(str1)):
if (str1[i] == '1') :
str1Ones += 1
elif (str1[i] == '0') :
str1Zeros += 1
if (str2[i] == '1') :
str2Ones += 1
elif (str2[i] == '0') :
str2Zeros += 1
# If the number of 1's and 0's
# are not same of the strings str1
# and str2 then print not possible
if (str1Zeros != str2Zeros and str1Ones != str2Ones) :
print("Not Possible")
else :
# Traversing through the
# strings str1 and str2
for i in range(len(str1)):
# If the str1 character not
# equals to str2 character
if (str1[i] != str2[i]) :
# Swaps 0 with 1 of the
# string str1
if (str1[i] == '0' and curStr1Ones > 0) :
str1[i] = '1'
curStr1Ones -= 1
# Breaks the loop as the count
# of 1's is zero. Hence, no swaps possible
if (str1[i] == '0' and curStr1Ones == 0) :
flag += 1
break
# Swaps 1 with 0 in the string str1
if (str1[i] == '1' and str2[i] == '0') :
str1[i] = '0'
curStr1Ones += 1
if (flag == 0) :
print("Possible")
# Print not possible
else :
print("Not Possible")
# Driver Code
# Given Strings
str1 = "0110"
str2 = "0011"
# Function Call
isBinaryStringsEqual(str1, str2)
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Text;
class GFG
{
// Function to check if it is possible to make
// two binary strings equal by given operations
static void isBinaryStringsEqual(string str1,
string str2)
{
// Stores count of 1's and 0's
// of the string str1
int str1Zeros = 0, str1Ones = 0;
// Stores count of 1's and 0's
// of the string str2
int str2Zeros = 0, str2Ones = 0;
int flag = 0;
// Stores current count of 1's
// present in the string str1
int curStr1Ones = 0;
// Count the number of 1's and 0's
// present in the strings str1 and str2
for (int i = 0; i < str1.Length; i++)
{
if (str1[i] == '1')
{
str1Ones++;
}
else if (str1[i] == '0')
{
str1Zeros++;
}
if (str2[i] == '1')
{
str2Ones++;
}
else if (str2[i] == '0')
{
str2Zeros++;
}
}
// If the number of 1's and 0's
// are not same of the strings str1
// and str2 then print not possible
if (str1Zeros != str2Zeros
&& str1Ones != str2Ones)
{
Console.WriteLine("Not Possible");
}
else
{
// Traversing through the
// strings str1 and str2
for (int i = 0; i < str1.Length; i++)
{
// If the str1 character not
// equals to str2 character
if (str1[i] != str2[i])
{
// Swaps 0 with 1 of the
// string str1
if (str1[i] == '0' && curStr1Ones > 0)
{
StringBuilder sb
= new StringBuilder(str1);
sb[i] = '1';
str1 = sb.ToString();
curStr1Ones--;
}
// Breaks the loop as the count
// of 1's is zero. Hence, no swaps
// possible
if (str1[i] == '0'
&& curStr1Ones == 0)
{
flag++;
break;
}
// Swaps 1 with 0 in the string str1
if (str1[i] == '1' && str2[i] == '0')
{
StringBuilder sb
= new StringBuilder(str1);
sb[i] = '0';
str1 = sb.ToString();
curStr1Ones++;
}
}
}
if (flag == 0)
{
Console.WriteLine("Possible");
}
// Print not possible
else
{
Console.WriteLine("Not Possible");
}
}
}
// Driver Code
static public void Main()
{
// Given Strings
string str1 = "0110";
string str2 = "0011";
// Function Call
isBinaryStringsEqual(str1, str2);
}
}
// This code is contributed by dharanendralv23
Javascript
<script>
// JavaScript program for the above approach
// Function to check if it is possible to make
// two binary strings equal by given operations
function isBinaryStringsEqual(list1, list2) {
var str1 = list1.split("");
var str2 = list2.split("");
// Stores count of 1's and 0's
// of the string str1
var str1Zeros = 0,
str1Ones = 0;
// Stores count of 1's and 0's
// of the string str2
var str2Zeros = 0,
str2Ones = 0;
var flag = 0;
// Stores current count of 1's
// present in the string str1
var curStr1Ones = 0;
// Count the number of 1's and 0's
// present in the strings str1 and str2
for (var i = 0; i < str1.length; i++) {
if (str1[i] === "1") {
str1Ones++;
} else if (str1[i] === "0") {
str1Zeros++;
}
if (str2[i] === "1") {
str2Ones++;
} else if (str2[i] === "0") {
str2Zeros++;
}
}
// If the number of 1's and 0's
// are not same of the strings str1
// and str2 then print not possible
if (str1Zeros !== str2Zeros && str1Ones !== str2Ones) {
document.write("Not Possible");
} else {
// Traversing through the
// strings str1 and str2
for (var i = 0; i < str1.length; i++) {
// If the str1 character not
// equals to str2 character
if (str1[i] !== str2[i]) {
// Swaps 0 with 1 of the
// string str1
if (str1[i] === "0" && curStr1Ones > 0) {
str1[i] = "1";
curStr1Ones--;
}
// Breaks the loop as the count
// of 1's is zero. Hence, no swaps
// possible
if (str1[i] === "0" && curStr1Ones === 0) {
flag++;
break;
}
// Swaps 1 with 0 in the string str1
if (str1[i] === "1" && str2[i] === "0") {
str1[i] = "0";
curStr1Ones++;
}
}
}
if (flag === 0) {
document.write("Possible");
}
// Print not possible
else {
document.write("Not Possible");
}
}
}
// Driver Code
// Given Strings
var str1 = "0110";
var str2 = "0011";
// Function Call
isBinaryStringsEqual(str1, str2);
</script>
Producción
Possible
Complejidad de tiempo: O(|str1|)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA