Find all N-digit binary numbers with equal sum of left and right half. N varies from [1-9] and binary number should not start with 0.

**6-digit numbers** with equal sum of left and right half

100001 100010 101011 110011 100100 101101 101110 110101 110110 111111

**7-digit numbers** with equal sum of left and right half

(mid element can be 0 or 1 for odd numbers)

1000001 1001001 1000010 1001010 1010011 1011011 1100011 1101011 1000100 1001100

1010101 1011101 1010110 1011110 1100101 1101101 1100110 1101110 1110111 1111111

A simple solution would be to generate all N-digit binary numbers and print only those numbers that satisfies the given constraints. The complexity of this solution would be exponential.

A **better solution** would be to generate only those N-digit numbers that satisfies the given constraints. The idea is to use recursion to form left and right half of the binary number. At each point in the recursion, we append 0 and 1 to the partially formed left & right half and recuse with one less bit in both the halves. We also maintain a variable to store difference between sum of bits in partially formed left and right half. If we have filled N/2-digits in both left and right half and the difference is 0, we print the binary number formed by left and right half. If the number is odd, the mid element can be either 0 or 1 i.e. the binary number is formed by (left half + mid + right half).

One optimization here is if the difference between left and right half becomes more than the number of bits left to be filled at any point in the recursion, we return as solution is not possible by following the current path. Also, we need to handle one special case that the binary number should not start with 0.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include <iostream> using namespace std; // Function to find all N-digit binary numbers with equal sum of // first and second half bits in Bottom-up manner void binarySeq(string left, string right, int n, int diff) { // return if number is invalid if (n > 9) return; // if number is less than N-digit and we can cover the difference // with n-digits left if (n && (2 * abs(diff) <= n)) { // if N is odd, recuse with mid as '0' and '1' if (n == 1) { binarySeq(left, "0" + right, 0, diff); binarySeq(left, "1" + right, 0, diff); return; } // special case - binary number should not start with 0 if (left != "") { // append 0 to both left and right half // both left and right sum remains unchanged binarySeq(left + "0", right + "0", n - 2, diff); // append 0 to left half and 1 to the right half // minus 1 from diff as right sum is increased by 1 binarySeq(left + "0", right + "1", n - 2, diff - 1); } // append 1 to left half and 0 to the right half // add 1 to diff as left sum is increased by 1 binarySeq(left + "1", right + "0", n - 2, diff + 1); // append 1 to both left and right half // both left and right sum remains unchanged binarySeq(left + "1", right + "1", n - 2, diff); } // if number becomes N-digit with equal sum of left and right // half, print it else if (n == 0 && diff == 0) cout << left + right << " "; } // Find all N-digit binary numbers with equal sum of left and right half int main() { int n = 6; // N-digit string left, right; // stores left and right half of binary number int diff = 0; // difference between left and right half binarySeq(left, right, n, diff); return 0; } |

**Output: **

100001 100010 101011 110011 100100 101101 101110 110101 110110 111111

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply