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

Download   Run Code

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

Download   Run Code

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

Notify of
avatar
Sort by:   newest | oldest | most voted
Matt Wanderman
Matt Wanderman

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

Charles Lin
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.

Neil Smith
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.… Read more »
wpDiscuz