# Generate Binary Numbers

Posted: 16 Dec, 2020

Difficulty: Easy

#### Your friend Ninja has been learning about binary numbers lately. In order to understand binary numbers with perfection, Ninja asks you to generate a list of binary numbers from 1 to ‘N’, which he can use later for reference.

#### For every integer Ninja gives, your task is to generate all the binary numbers from 1 to ‘N’.

#### Example:

```
Consider N = 5,
All the binary numbers from 1 to 5 are: 1, 10, 11, 100, 101.
```

##### Input format:

```
The very first line of input contains an integer ‘T’ denoting the number of test cases.
The first and the only line of every test case contains a positive integer ‘N’.
```

##### Output format:

```
For each test case, print ‘N’ space-separated binary numbers from 1 to ‘N’, in a separate line.
Print the output of each test case in a separate line.
```

##### Note:

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints:

```
1 <= T <= 10
1 <= N <= 10 ^ 5
Time Limit: 1 sec
```

Approach 1

The idea is to generate all the decimal numbers from 1 to **N** and convert each of them to their corresponding binary representation.

This can be done as follows:

- Loop through all the decimal numbers from 1 to
**N**. - During each iteration, convert the decimal number to its corresponding binary representation.
- The algorithm to convert a decimal number to binary is as follows:
- Divide the number by 2 and store its remainder.
- Repeat the previous step until the number is greater than 0.
- Now, create a string of the remainders in reverse of the order in which they were obtained.
- Print the string, which is the binary representation of your decimal number.

Approach 2

The idea is to recognize the pattern while generating the sequence of the binary numbers. The following image can help us identify the pattern easily.

→ The number in blue color represents the decimal form of the binary number present inside the circle:

- The first binary number, i.e. ‘1’ is generated manually.
- Now, if we append ‘0’ and ‘1’ to our previously generated number ‘1’, we get the next two binary numbers of the sequence, which are
**10**and**11**. - Appending ‘0’ and ‘1’ to these two newly generated binary numbers gives us the next four binary numbers of the sequence, which are
**100, 101, 110, 111**. - Hence, repeating the same procedure again, we can generate all the binary numbers in an efficient manner.
- So, in order to generate the required sequence, we can assume that we are performing a level-order traversal of the tree until we get all the numbers from 1 to
**N**.

**The algorithm for the approach is as follows:**

- Create an empty queue to store the binary numbers.
- Enqueue with the first binary number which we want to generate i.e. ‘1’.
- Now, repeat the following steps until
**N**numbers have been generated:- Dequeue the front element of the queue. Store this element in a variable that says
**‘E’**. - Print
**‘E’**. - Append ‘0’ to the end of
**‘E’**and push it back to the queue. - Append ‘1’ to the end of
**‘E’**and push it back to the queue.

- Dequeue the front element of the queue. Store this element in a variable that says

SIMILAR PROBLEMS

# Game of 3

Posted: 11 Jul, 2021

Difficulty: Easy

# Lexicographic Permutation Rank

Posted: 13 Jul, 2021

Difficulty: Moderate

# Zero Pair Sum

Posted: 22 Jul, 2021

Difficulty: Moderate

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy

# Remove K Corner Elements

Posted: 31 Jul, 2021

Difficulty: Easy