Find all N-digit binary numbers with equal sum of bits in its two halves

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.

 

For example,


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

Download   Run Code

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

Notify of
avatar
wpDiscuz