Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

How to print the first n numbers with exactly two set bits

Fatima Numan

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Problem statement

if we are given n numbers, how can we visualize these numbers in binary forms?

A set bit is a bit that is written as "1" in the binary form of a number. For example, numbers with exactly three set bits will look like 0111, 1110, 1011, 1101, etc.

Conditions

The condition for the numbers we want to print is that there must be exactly two digits in their respective binary form. For example, binary numbers 3, 5, and 6 are written as 11, 101, and 110, respectively. These numbers have exactly two sets of bits. And numbers like 1, 2, 4, etc., do not satisfy this condition because, in binary, they are written as 01, 10, and 100, respectively.

So we only need to print those numbers that satisfy the conditions above. We'll have an entry to determine the total number of such numbers we want to print.

For example, if we pass n = 4, the output would be:

This figure illustrates the problem described above for the input, n = 4.

The integer 10 is not part of the output. However, it satisfies the conditions of the given problem. Because the entries (the limit on the total number of integers to be printed) are chosen to be four.

Solutions

We can consider two solutions for this problem:

Naive approach

A naive approach is to take into consideration only those numbers whose binary form starts with 1. Then we can check if another "1" exists in the binary representation of the number. For example, the number 5 in binary is 101. It starts with 1, so we have our first required set bit. Then we'll check for another set bit and print it.

We might get the required result, but this is not a desirable approach.

Efficient approach

In this approach, we can consider the fact that numbers in their binary forms are simply powers of two, changing based on the set bits as they go higher. For example, 21=0012^1=001 , 22=0102^2=010, 23=1002^3=100and so on.

So, we can first initialize the higher of the two set bits (power of 2) and then take into consideration the lower set bits for the current higher set bit while decrementing n for all the required numbers, we find exactly two set bits.

Code example

Let's look at the code in C++ and Python3:

#include <iostream>
using namespace std;
void getTwoSetNumbers(int n) //defining the function
{
int number = 1; //the counter of the number being printed
int higher = 1; //the higher set bit declared
cout << "The required numbers are:" << endl;
while (n > 0)
//while we do not reach the required limit of numbers to be printed
{
int lower = 0; //the lower set bit declared
while (lower < higher)
//until all lower set bit numbers below the higher set bit are not printed
{
n--; //decrementing n
cout << "Number " << number << " => ";
int output = (1 << higher) + (1 << lower); //converting the bits into the required number
number++;
lower++; //incrementing the lower set bit to the next number to be printed
cout << output << " " << endl;
if (n == 0) //if the limit of the numbers to be printed is reached
break;
}
higher++; //incrementing to the next higher set bit
if (n == 0)
break;
}
}
int main()
{
getTwoSetNumbers(6); //function call for n = 6
return 0;
}

Code explanation

In the code provided above, the variable higher specifies the higher set bit and the variable lower is the lower set bit, which keeps on incrementing until its value gets greater than higher , while the numbers with exactly two set bits get printed. For the algorithm to stop, the limit n provided by the user will keep on decrementing until it reaches zero.

The variable, output has been specified to store the number to be printed by combining the values of the lower and higher set bits, added by 1.

Once n = 0, the loops break/function returns, and the numbers stop printing.

Time complexity

The time complexity for the algorithm above is O(n)O(n).

RELATED TAGS

CONTRIBUTOR

Fatima Numan
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring