http://www.techiedelight.com/find-n-digit-binary-numbers-having-more-one-than-zero/
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
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.
// 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);
}
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 –
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);
}
}
