Generate All Binary Numbers in the Range [L, R]

Intuition

This is a relatively simple problem to solve. We'll calculate the length of the binary representation of the greatest integer, 'R,' because binary numbers should all be the same length.

After we have the length of the binary representation, we will generate binary strings for each number from 'L' to 'R' of length 'MX_LEN'. 

Approach

As we are clear with our approach now, we'll be writing two functions, findBinaryInRangeLR() which return the vector of binary strings in the range [L, R] and decimalToBinary() which converts a decimal number into its binary string of length ‘MX_LEN’.

findBinaryInRangeLR()

Parameters

1. ‘L’ - Lower bound.
2. ‘R’ - Upper bound.

Working

1. Calculate the value of ‘MX_LEN’.
2. Next, initialize the vector of strings to store the answer.
3. Now, loop from ‘L’ to ‘R’ and generate binary strings for each number using the function decimalToBinary().
4. Return the answer.

decimalToBinary()

Parameters

1. ‘NUM’ - Decimal number that is to be converted.
2. ‘LEN’ - Length of the binary string to be generated.

Working

1. Initialize the answer binary string 'BINARY'.
2. Loop until ‘NUM’ is not zero, and concatenate the last bit into ‘BINARY’.
3. Update ‘NUM = NUM >> 1’.
4. Check if the length of the binary string is smaller than ‘LEN’, concatenate extra ‘LEN - BINARY.size()’ zeros to the binary string.
5. Reverse the string ‘BINARY’ and return.
    

Must Read Lower Bound in C++, and Euclid GCD Algorithm

Program

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

// Convert decimal number to binary of specified length.
string decimalToBinary(int num, int len)
{
   // Declare a string to store the binary number.
   string binary;
   
   // Loop until ‘NUM’ is not zero.
   while (num != 0)
   {
       // Concatenate the last bit.
       binary += to_string(num & 1);
       
       // Right shift 'NUM'.
       num = num >> 1;
   }
   
   // If the length of the binary string is less than ‘LEN’, add extra zeros.
   if (binary.length() < len)
   {
       int extra = len - binary.size();
       while (extra--)
       {
           binary += "0";
       }
   }
   
   // Reverse the 'BINARY' string.
   reverse(binary.begin(), binary.end());
   
   // Return.
   return binary;
}

// Function to generate all binary numbers in the range [L, R] with the same length.
vector<string> findBinaryInRangeLR(int l, int r)
{
   // Max Length of the binary strings.
   int mxLen = (int)ceil(log(r + 1) / log(2));
   
   // Declare the 'RES_LIST' to store the list of binary strings in the range [L, R].
   vector<string> resList;
   
   // Loop from 'L' to 'R'.
   for (int i = l; i <= r; i++)
   {
       // Find the binary string for 'i' of length 'MX_LEN', then push it into the answer.
       resList.emplace_back(decimalToBinary(i, mxLen));
   }
   
   // Return.
   return resList;
}

int main()
{
   int l, r;
   cout << "Enter the value of L, R: ";
   cin >> l >> r;
   vector<string> binaryList = findBinaryInRangeLR(l, r);
   cout << "All Binary Numbers in Range [L, R]:\n";
   for (string &binaryString : binaryList)
   {
       cout << binaryString << "\n";
   }
   cout << endl;
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the value of L, R: 10 24

Output

All Binary Numbers in Range [L, R]:
01010
01011
01100
01101
01110
01111
10000
10001
10010
10011
10100
10101
10110
10111
11000

Time Complexity

O((R - L) * MX_LEN), where ‘MX_LEN = ceil(log2(R+1))’, L = lower bound and R = upper bound.

We loop from ‘L’ to ‘R’ and generate a binary string for each number whose length can be a maximum of ‘MX_LEN’. Hence time complexity = ((R - L) * MX_LEN).

Space Complexity

O(1).

As we are not using any auxiliary space.

Must read decimal to binary c++ 

Key Takeaways

In the above blog, we’ve seen how maths concepts can be so important while solving DSA problems. At Coding Ninjas, we have a guided path for maths needed for DSA. Do check it out.

On the Coding Ninjas Platform, we have various such problems and blogs. Additionally, Coding Ninjas recently introduced the Coding Ninjas Studio Test Series, a mainly developed test series for acing tech interviews.

Thanks for reading. I hope you’ve gained a lot from this blog.