Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Intuition
4.
Approach
4.1.
Program
4.2.
Input
4.3.
Output
4.4.
Time Complexity
4.5.
Space Complexity
5.
Key Takeaways
Last Updated: Mar 27, 2024

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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

There is an algorithm for anything, from inverting a binary tree to proposing somebody. Although computer algorithms are not novels, people read them as if they are. However, they are mathematics written uniquely.

"An algorithm must be seen to be believed," said Sir Donald Knuth. The most straightforward approach to learning an algorithm is to write it instead of reading it. So grab a notepad and pen and join us in discussing the logic.

The problem we will discuss today is a bit of knowledge of decimal to binary conversion.

Problem Statement

You are given two integers, 'L' and 'R'. Generate all binary numbers in the range [L, R] with the same length.

Example

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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.

Previous article
Binary Numbers of N digits
Next article
Find a Number X Such that XOR of Given Array after Adding X to Each Element is 0
Live masterclass