Problem of the day
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.
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.
1 <= T <= 10
1 <= N <= 10 ^ 5
Time Limit: 1 sec
2
2
6
1 10
1 10 11 100 101 110
For the first test case when N = 2.
We need all the binary numbers from 1 to 2:
1 -> 1
2 -> 10
Thus, the output is 1, 10.
For the second test case when N = 6
We need all the binary numbers from 1 to 6:
1 -> 1
2 -> 10
3 -> 11
4 -> 100
5 -> 101
6 -> 110
Thus, the output is 1, 10, 11, 100, 101, 110.
2
8
4
1 10 11 100 101 110 111 1000
1 10 11 100
A simple and intuitive approach could be to generate all the decimal numbers from 1 to N and convert each of them to their corresponding binary representation.
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:
O(N * log(N)), where N is the given positive integer.
In the worst case, we convert every decimal number from 1 to N to its binary form, each conversion requires O(log(N)) operations. Hence, the overall Time Complexity is O(N * log(N)).
O(log(N)), where N is the given positive integer.
In the worst case, the Space Complexity O(log(N)) is required to store the intermediate result of the conversion of decimal(N) to binary(N). Hence, the overall Space Complexity is O(log(N)).