Dado un número n, necesitamos imprimir todos los números binarios de n dígitos con la misma suma en mitades izquierda y derecha. Si n es impar, entonces el elemento medio puede ser 0 o 1.
Ejemplos:
Input : n = 4 Output : 0000 0101 0110 1001 1010 1111 Input : n = 5 Output : 00000 00100 01001 01101 01010 01110 10001 10101 10010 10110 11011 11111
La idea es construir recursivamente las mitades izquierda y derecha y realizar un seguimiento de la diferencia entre las cuentas de 1 en ellas. Imprimimos una string cuando la diferencia se convierte en 0 y no hay más caracteres para agregar.
C++
// C++ program to generate all binary strings with // equal sums in left and right halves. #include <bits/stdc++.h> using namespace std; /* Default values are used only in initial call. n is number of bits remaining to be filled di is current difference between sums of left and right halves. left and right are current half substrings. */ void equal(int n, string left="", string right="", int di=0) { // TWO BASE CASES // If there are no more characters to add (n is 0) if (n == 0) { // If difference between counts of 1s and // 0s is 0 (di is 0) if (di == 0) cout << left + right << " "; return; } /* If 1 remains than string length was odd */ if (n == 1) { // If difference is 0, we can put remaining // bit in middle. if (di == 0) { cout << left + "0" + right << " "; cout << left + "1" + right << " "; } return; } /* If difference is more than what can be be covered with remaining n digits (Note that lengths of left and right must be same) */ if ((2 * abs(di) <= n)) { /* add 0 to end in both left and right half. Sum in both half will not change*/ equal(n-2, left+"0", right+"0", di); /* add 0 to end in both left and right half* subtract 1 from di as right sum is increased by 1*/ equal(n-2, left+"0", right+"1", di-1); /* add 1 in end in left half and 0 to the right half. Add 1 to di as left sum is increased by 1*/ equal(n-2, left+"1", right+"0", di+1); /* add 1 in end to both left and right half the sum will not change*/ equal(n-2, left+"1", right+"1", di); } } /* driver function */ int main() { int n = 5; // n-bits equal(n); return 0; }
Java
// Java program to generate all binary strings // with equal sums in left and right halves. import java.util.*; class GFG { // Default values are used only in initial call. // n is number of bits remaining to be filled // di is current difference between sums of // left and right halves. // left and right are current half substrings. static void equal(int n, String left, String right, int di) { // TWO BASE CASES // If there are no more characters to add (n is 0) if (n == 0) { // If difference between counts of 1s and // 0s is 0 (di is 0) if (di == 0) System.out.print(left + right + " "); return; } /* If 1 remains than string length was odd */ if (n == 1) { // If difference is 0, we can put // remaining bit in middle. if (di == 0) { System.out.print(left + "0" + right + " "); System.out.print(left + "1" + right + " "); } return; } /* If difference is more than what can be be covered with remaining n digits (Note that lengths of left and right must be same) */ if ((2 * Math.abs(di) <= n)) { // add 0 to end in both left and right // half. Sum in both half will not // change equal(n - 2, left + "0", right + "0", di); // add 0 to end in both left and right // half* subtract 1 from di as right // sum is increased by 1 equal(n - 2, left + "0", right + "1", di - 1); // add 1 in end in left half and 0 to the // right half. Add 1 to di as left sum is // increased by 1* equal(n - 2, left + "1", right + "0", di + 1); // add 1 in end to both left and right // half the sum will not change equal(n - 2, left + "1", right + "1", di); } } // Driver Code public static void main(String args[]) { int n = 5; // n-bits equal(n, "", "", 0); } } // This code is contributed // by SURENDRA_GANGWAR
Python3
# Python program to generate all binary strings with # equal sums in left and right halves. # Default values are used only in initial call. # n is number of bits remaining to be filled # di is current difference between sums of # left and right halves. # left and right are current half substrings. def equal(n: int, left = "", right = "", di = 0): # TWO BASE CASES # If there are no more characters to add (n is 0) if n == 0: # If difference between counts of 1s and # 0s is 0 (di is 0) if di == 0: print(left + right, end = " ") return # If 1 remains than string length was odd if n == 1: # If difference is 0, we can put remaining # bit in middle. if di == 0: print(left + "0" + right, end = " ") print(left + "1" + right, end = " ") return # If difference is more than what can be # be covered with remaining n digits # (Note that lengths of left and right # must be same) if 2 * abs(di) <= n: # add 0 to end in both left and right # half. Sum in both half will not # change equal(n - 2, left + "0", right + "0", di) # add 0 to end in both left and right # half* subtract 1 from di as right # sum is increased by 1 equal(n - 2, left + "0", right + "1", di - 1) # add 1 in end in left half and 0 to the # right half. Add 1 to di as left sum is # increased by 1 equal(n - 2, left + "1", right + "0", di + 1) # add 1 in end to both left and right # half the sum will not change equal(n - 2, left + "1", right + "1", di) # Driver Code if __name__ == "__main__": n = 5 # n-bits equal(5) # This code is contributed by # sanjeev2552
C#
// C# program to generate all binary strings // with equal sums in left and right halves. using System; class GFG { // Default values are used only in initial call. // n is number of bits remaining to be filled // di is current difference between sums of // left and right halves. // left and right are current half substrings. static void equal(int n, String left, String right, int di) { // TWO BASE CASES // If there are no more characters // to add (n is 0) if (n == 0) { // If difference between counts of 1s // and 0s is 0 (di is 0) if (di == 0) Console.Write(left + right + " "); return; } /* If 1 remains than string length was odd */ if (n == 1) { // If difference is 0, we can put // remaining bit in middle. if (di == 0) { Console.Write(left + "0" + right + " "); Console.Write(left + "1" + right + " "); } return; } /* If difference is more than what can be be covered with remaining n digits (Note that lengths of left and right must be same) */ if ((2 * Math.Abs(di) <= n)) { // add 0 to end in both left and right // half. Sum in both half will not // change equal(n - 2, left + "0", right + "0", di); // add 0 to end in both left and right // half* subtract 1 from di as right // sum is increased by 1 equal(n - 2, left + "0", right + "1", di - 1); // add 1 in end in left half and 0 to the // right half. Add 1 to di as left sum is // increased by 1* equal(n - 2, left + "1", right + "0", di + 1); // add 1 in end to both left and right // half the sum will not change equal(n - 2, left + "1", right + "1", di); } } // Driver Code public static void Main(String []args) { int n = 5; // n-bits equal(n, "", "", 0); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript program to generate all binary strings // with equal sums in left and right halves. // Default values are used only in initial call. // n is number of bits remaining to be filled // di is current difference between sums of // left and right halves. // left and right are current half substrings. function equal(n,left,right,di) { // TWO BASE CASES // If there are no more characters to add (n is 0) if (n == 0) { // If difference between counts of 1s and // 0s is 0 (di is 0) if (di == 0) document.write(left + right + " "); return; } /* If 1 remains than string length was odd */ if (n == 1) { // If difference is 0, we can put // remaining bit in middle. if (di == 0) { document.write(left + "0" + right + " "); document.write(left + "1" + right + " "); } return; } /* If difference is more than what can be be covered with remaining n digits (Note that lengths of left and right must be same) */ if ((2 * Math.abs(di) <= n)) { // add 0 to end in both left and right // half. Sum in both half will not // change equal(n - 2, left + "0", right + "0", di); // add 0 to end in both left and right // half* subtract 1 from di as right // sum is increased by 1 equal(n - 2, left + "0", right + "1", di - 1); // add 1 in end in left half and 0 to the // right half. Add 1 to di as left sum is // increased by 1* equal(n - 2, left + "1", right + "0", di + 1); // add 1 in end to both left and right // half the sum will not change equal(n - 2, left + "1", right + "1", di); } } // Driver Code let n = 5; // n-bits equal(n, "", "", 0); // This code is contributed by rag2127 </script>
Producción:
10001 10101 10010 10110 11011 11111
Este artículo es una contribución de Pranav . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA