Dado un número entero N , la tarea es generar todas las strings binarias con ceros y unos iguales . Si no hay strings posibles, imprima -1
Ejemplos:
Entrada : N = 2
Salida: “01”, “10”
Explicación : Todas las strings binarias posibles de longitud 2 son: 01, 10, 11, 00. De estas, solo 2 tienen el mismo número de 0 y 1Entrada: 4
Salida: “0011”, “0101”, “0110”, “1100”, “1010”, “1001”
Enfoque: La tarea se puede resolver usando recursividad. Si N es impar , entonces la respuesta es -1 , de lo contrario, podemos usar la recursividad para generar todas las strings binarias con ceros y unos iguales . Siga los pasos a continuación para resolver el problema:
- Los unos variables mantienen un registro del número de 1 y los ceros variables mantienen un registro del número de 0 en la string.
- Tanto los unos como los ceros deben tener una frecuencia N/2 .
- Condición base: la string s almacena la string de salida . Entonces, cuando la longitud de s llega a N , detenemos las llamadas recursivas e imprimimos la string de salida s .
- Si la frecuencia de los 1 es menor que N/2 , agregue 1 a la string e incremente en unidades .
- Si la frecuencia de los 0 es menor que N/2 , agregue 0 a la string e incremente los ceros .
A continuación se muestra la implementación del código anterior:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Recursive function that prints // all strings of N length with equal 1's and 0's void binaryNum(int n, string s, int ones, int zeros) { // String s contains the output to be printed // ones stores the frequency of 1's // zeros stores the frequency of 0's // Base Condition: When the length of string s // becomes N if (s.length() == n) { cout << (s) << endl; return; } // If frequency of 1's is less than N/2 then // add 1 to the string and increment ones if (ones < n / 2) binaryNum(n, s + "1", ones + 1, zeros); // If frequency of 0's is less than N/2 then // add 0 to the string and increment zeros if (zeros < n / 2) binaryNum(n, s + "0", ones, zeros + 1); } // Driver Code int main() { string s = ""; binaryNum(4, s, 0, 0); return 0; } // This code is contributed by Potta Lokesh
Java
// Java program for the above approach import java.io.*; class GFG { // Recursive function that prints // all strings of N length with equal 1's and 0's static void binaryNum(int n, String s, int ones, int zeros) { // String s contains the output to be printed // ones stores the frequency of 1's // zeros stores the frequency of 0's // Base Condition: When the length of string s // becomes N if (s.length() == n) { System.out.println(s); return; } // If frequency of 1's is less than N/2 then // add 1 to the string and increment ones if (ones < n / 2) binaryNum(n, s + "1", ones + 1, zeros); // If frequency of 0's is less than N/2 then // add 0 to the string and increment zeros if (zeros < n / 2) binaryNum(n, s + "0", ones, zeros + 1); } // Driver Code public static void main(String[] args) { String s = ""; binaryNum(4, s, 0, 0); } }
Python3
# python code for the above approach # Recursive function that prints # all strings of N length with equal 1's and 0's def binaryNum(n, s, ones, zeros): # String s contains the output to be printed # ones stores the frequency of 1's # zeros stores the frequency of 0's # Base Condition: When the length of string s # becomes N if (len(s) == n): print(s) return # If frequency of 1's is less than N/2 then # add 1 to the string and increment ones if (ones < n / 2): binaryNum(n, s + "1", ones + 1, zeros) # If frequency of 0's is less than N/2 then # add 0 to the string and increment zeros if (zeros < n / 2): binaryNum(n, s + "0", ones, zeros + 1) # Driver Code if __name__ == "__main__": s = "" binaryNum(4, s, 0, 0) # This code is contributed by rakeshsahni
C#
// C# program for the above approach using System; class GFG { // Recursive function that prints // all strings of N length with equal 1's and 0's static void binaryNum(int n, string s, int ones, int zeros) { // String s contains the output to be printed // ones stores the frequency of 1's // zeros stores the frequency of 0's // Base Condition: When the length of string s // becomes N if (s.Length == n) { Console.WriteLine(s); return; } // If frequency of 1's is less than N/2 then // add 1 to the string and increment ones if (ones < n / 2) binaryNum(n, s + "1", ones + 1, zeros); // If frequency of 0's is less than N/2 then // add 0 to the string and increment zeros if (zeros < n / 2) binaryNum(n, s + "0", ones, zeros + 1); } // Driver Code public static void Main(string[] args) { string s = ""; binaryNum(4, s, 0, 0); } } // This code is contributed by ukasp.
Javascript
<script> // javascript program for the above approach // Recursive function that prints // all strings of N length with equal 1's and 0's function binaryNum(n, s, ones, zeros) { // String s contains the output to be printed // ones stores the frequency of 1's // zeros stores the frequency of 0's // Base Condition: When the length of string s // becomes N if (s.length == n) { document.write(s+"<br>"); return; } // If frequency of 1's is less than N/2 then // add 1 to the string and increment ones if (ones < n / 2) binaryNum(n, s + "1", ones + 1, zeros); // If frequency of 0's is less than N/2 then // add 0 to the string and increment zeros if (zeros < n / 2) binaryNum(n, s + "0", ones, zeros + 1); } // Driver Code var s = ""; binaryNum(4, s, 0, 0); // This code is contributed by 29AjayKumar </script>
1100 1010 1001 0110 0101 0011
Complejidad de Tiempo : O(2 N )
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por amrithabpatil y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA