Trusted answers to developer questions

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.

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.

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:

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.

We can consider two solutions for this problem:

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.

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,

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.

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 printedint higher = 1; //the higher set bit declaredcout << "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 declaredwhile (lower < higher)//until all lower set bit numbers below the higher set bit are not printed{n--; //decrementing ncout << "Number " << number << " => ";int output = (1 << higher) + (1 << lower); //converting the bits into the required numbernumber++;lower++; //incrementing the lower set bit to the next number to be printedcout << output << " " << endl;if (n == 0) //if the limit of the numbers to be printed is reachedbreak;}higher++; //incrementing to the next higher set bitif (n == 0)break;}}int main(){getTwoSetNumbers(6); //function call for n = 6return 0;}

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.

The time complexity for the algorithm above is

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

Related Courses