# Find all N-digit binary numbers having more 1’s than 0’s for any prefix

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 (1001 has 2 zeros and 1 ones at 3rd position). 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 recurse 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.

## Java

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 –

## Java

Output:

1111
1110
1101
1100
1011
1010

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 🙂

Get great deals at Amazon

Subscribe
Notify of
Guest
Matt Wanderman

Why include the possibility of making an invalid number? I’m not sure how to format code here.
http://ideone.com/e9tSFC

Guest
Charles Lin

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.

Guest
Neil Smith

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.