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>
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