Print N-bit binary numbers having more 1’s than 0’s in all prefixes in C++

October 14, 2022

N-bit binary numbers having more  or equal 1’s than 0’s in C++

Here, in this page we will discuss the program to print n-bit binary numbers having more or equal 1’s than 0’s in C++ programming language. We are given with an integer value n, and need to print n-bit binary numbers.

Example :

  • Input : 4
  • Output : 1111 1110 1101 1100 1011 1010
  • Explanation : 1111 1110 1101 1100 1011 1010 all these are the requied binary numbers.
N-bit binary numbers having more 1’s than 0’s in C++

Method 1 (Recursive Approach) :

In this method we use recursion. At each point in the recursion, we append 0 and 1 to the partially formed number and recur with one less digit. 

  • Create a recursive function say printRec(string number, int extraOnes, int remainingPlaces)
  • Check if(remainingPlaces==0), if it is true then print number and return //Base condition
  • Otherwise call the function by appending “1” i.e, printRec(number + “1”, extraOnes+1, remainingPlaces-1)
  • Now, check if(extraOnes > 0),then call printRec(number+ “0”, extraOnes-1, remainingPlaces-1), i.e, by appending 0 to number.

Code to find N-bit binary numbers having more or equal 1's than 0's in C++

Run 

#include <bits/stdc++.h>
using namespace std;

//Recursive function to print the required numbers
void printRec(string number, int extraOnes,int remainingPlaces)
{
   if (remainingPlaces==0) {
     cout << number << " "; return; 
   } 
   printRec(number + "1", extraOnes + 1, remainingPlaces - 1);

   if (extraOnes > 0) 
   printRec(number + "0", extraOnes - 1,remainingPlaces - 1);
}

// Driver code
int main()
{
   int n = 4;

   string str = ""; 
   printRec(str, 0, n);

   return 0;
}


Output :


1111 1110 1101 1100 1011 1010

Method 2 (Using Non-Recursive Approach) :

In this method we will discuss the non-recursive approach to print the required binary numbers having more or equal1’s than 0’s.

  • Declare two variables say first and last.
  • Set first to 1<<(N-1) and last to first*2.
  • Run a loop over the range i.e, last-1 to first.
  • Now, quire only those which satisfies the condition (i.e, one_cnt >= zero_cnt)
N-bit binary numbers

Code in C++

Run 
#include <bits/stdc++.h>
using namespace std;

// Function to get the binary representation
// of the number N
string getBinaryRep(int N, int num_of_bits)
{
   string s = "";
   num_of_bits--;

   // loop for each bit
   while (num_of_bits >= 0)
   {
     if (N & (1 << num_of_bits))
        s.append("1");
     else
        s.append("0");
     num_of_bits--;
    }
    return s;
}


vector <string> NBitBinary(int N)
{
   vector <string> s;
   int first = 1 << (N - 1);
   int last = first * 2;

   for (int i = last - 1; i >= first; --i)
   {
      int zero_cnt = 0;
      int one_cnt = 0;
      int t = i;
      int num_of_bits = 0;

      // longest prefix check
      while (t)
      {
         if (t & 1)
           one_cnt++;
         else
           zero_cnt++;
         num_of_bits++;
         t = t >> 1;
      }

      if (one_cnt >= zero_cnt)
      {
          // do sub-prefixes check
          bool all_prefix_match = true;
          int msk = (1 << num_of_bits) - 2;
          int prefix_shift = 1;
          while (msk)
          {

               int prefix = (msk & i) >> prefix_shift;
               int prefix_one_cnt = 0;
               int prefix_zero_cnt = 0;
               while (prefix)
               {
                 if (prefix & 1)
                     prefix_one_cnt++;
                 else
                     prefix_zero_cnt++;
                 prefix = prefix >> 1;
               }
               if (prefix_zero_cnt > prefix_one_cnt)
               {
                  all_prefix_match = false;
                  break;
               }
               prefix_shift++;
               msk = msk & (msk << 1);
          }
          if (all_prefix_match)
          {
               s.push_back(getBinaryRep(i, num_of_bits));
          }
      }
   }
   return s;
}

// Driver code
int main()
{
      int n = 4;

      vector <string>results = NBitBinary(n);
      for (int i = 0; i < results.size(); ++i)
           cout << results[i] << " ";

      return 0;
}


Output :


1111 1110 1101 1100 1011 1010

Program for octal to decimal conversion

Program for hexadecimal to decimal conversion

Program for decimal to binary conversion

Program for decimal to octal conversion

Program for decimal to hexadecimal conversion

 

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime
Software Engineering SDLC

1 comments on “Print N-bit binary numbers having more 1’s than 0’s in all prefixes in C++”


  • amanbajpai5734

    C++ code
    #include
    using namespace std;

    //This function checks the no. of digits in an integer
    int checkDigit(int x)
    {
    int count=1;
    while(x/10!=0){
    x=x/10;
    count++;
    }
    return count;
    }

    //This function checks whether a number is binary or not
    bool checkBinary(int a)
    {
    while(a!=0)
    {
    int y=a%10;
    if(y!=0&&y!=1)
    return false;
    a=a/10;
    }
    return true;
    }

    //This function calculates the no. of zeroes and ones in an integer
    bool countOne(int a)
    {
    int count1=0;
    int count0=0;
    while(a!=0)
    {
    int y=a%10;
    if(y==1)
    count1++;
    else
    count0++;
    a=a/10;
    }
    if(count1>=count0)
    return true;
    else
    return false;
    }

    //This function checks the balancing of ones and zeroes in prefix of the string
    bool countOneinPrefix(int a)
    {
    while(a!=0)
    {
    if(countOne(a))
    {
    a=a/10;
    countOneinPrefix(a);
    }
    else{
    return false;
    }
    }
    return true;
    }

    //The driver function
    int main()
    {
    int x;
    string s2;
    cout<>x;
    for(int i=0;i<x;i++)
    s2 = s2 + "1";
    int num2 = stoi(s2);

    for(int i=0;i<=num2;i++)
    {
    if(checkDigit(i)==x)
    {
    if(checkBinary(i)){
    if(countOneinPrefix(i))
    cout<<i<<endl;
    }
    }
    }
    return 0;
    }