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 🙂

Thanks for a good library of puzzles and solutions!

I think your test cases, and therefore implementation, are wrong in this case. For 4-bit numbers, what about 1001? or 0111?

I think that, rather than counting ones and zeroes used, you need only count the zeroes remaining to be used. That gives you a recursive solution with two base cases: If the partial string is long enough, return it; if you’ve used all the zeroes, pad the partial string with ones. The recursive case finds the strings with a zero and a one added to the string, with the remaining length and zero budget updated accordingly.

`def build_numbers(remaining_length, prefix=None, zeroes_remaining=None):`

if prefix is None: prefix = ""

if zeroes_remaining is None: zeroes_remaining = int(remaining_length / 2.0)

if remaining_length == 0:

return [prefix]

elif zeroes_remaining == 0:

return [prefix + "1" * remaining_length]

else:

return (build_numbers(remaining_length - 1, prefix + "0", zeroes_remaining - 1)

+

build_numbers(remaining_length - 1, prefix + "1", zeroes_remaining) )

Hi Neil, Thanks for sharing your concern. If you take a look at the problem statement again, it states that – “N-digit binary numbers having

more 1’s than 0’s at any positionin the number”So, 1001 violates the problem constraints as 1001 has 2 zeros and 1 ones at 3rd position. Similarly 0111 has 1 zero and 0 ones at 1st position itself.

Hope we have made it clear now. We will also update the problem statement to make context more clear. Happy coding 🙂

Oh, OK. If I understand you, you’re saying the problem is to find a sequence of ones and zeros such that all prefixes of the sequence have at least as many ones as zeros. I thought the problem description meant a constraint on the final sequence, when it was considered a bag (multiset).