Given a positive integer N, find all N-digit binary numbers having more 1’s than 0’s for any prefix of the number.

For example, for N = 4 the binary numbers satisfies the given constraints are

1111

1110

1101

1100

1011

1010

1001 will not form part of the solution as it violates the problem constraints (prefix 100 has 2 zeros and 1 ones). Same applies for all other 4-digit binary numbers.

A simple solution would be to generate all N-digit 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. At each point in the recursion, we append 0 and 1 to the partially formed number and recuse with one less digit. We also maintain count of number of zeroes and number of ones in the partially formed number. The optimization here is if number of ones are less than number of zeroes at any point in the recursion, we return.

## 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 |
#include <iostream> using namespace std; // Function to find all N-digit binary numbers having // more 1's than 0's at any position void find(string str, int n, int zeros, int ones) { // continue only if number of ones are more than equal // to number of zeroes if (ones < zeros) return; // if number becomes N-digit, print it if (n == 0) { cout << str << endl; return; } // append 1 to the result and recuse with one less digit find(str + "1", n - 1, zeros, ones + 1); // append 0 to the result and recuse with one less digit find(str + "0", n - 1, zeros + 1, ones); } // main function int main() { // given number of digits int n = 4; string str; find(str, n, 0, 0); return 0; } |

**Output: **

1111

1110

1101

1100

1011

1010

As mentioned by Matt in comments below, we can improve above code by excluding the possibility of making an invalid number. Below is the code that does the task –

## 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 |
#include <iostream> #include <string> // Function to find all N-digit binary numbers having // more 1's than 0's at any position void Solution(std::string currentNumber, int extraOnes, int remainingPlaces) { // If the number is completed, print it if (0 == remainingPlaces) { std::cout << currentNumber << std::endl; return; } // Append 1 to the current number and reduce the remaining places by one Solution(currentNumber + "1", extraOnes + 1, remainingPlaces - 1); // If there are more ones than zeroes, append 0 to the current number // and reduce the remaining places by one if (0 < extraOnes) { Solution(currentNumber + "0", extraOnes - 1, remainingPlaces - 1); } } // main function int main() { const int numberOfDigits = 4; std::string str; Solution(str, 0, numberOfDigits); return 0; } |

**Output: **

1111

1110

1101

1100

1011

1010

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

Why include the possibility of making an invalid number? I’m not sure how to format code here.

http://ideone.com/e9tSFC

Matt, thanks for your solution. We will soon add this to the post. The time complexity remains almost same though.

you can enclose your code within <pre></pre> tag. It preserves both spaces and line breaks. You can also use ideone.com and post solution link here. We have edited your comment.

I feel the problem statement isn’t clear enough at first glance, especially the phrase “at any position in the number”.

Something like “any substring starting from position 0” or “any prefix of the number” would be clearer I think.

Charles, we have updated the problem statement. Happy coding 🙂