Solution: Generate Binary Numbers from 1 to N

Grokking Data Structures & Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Generate Binary Numbers from 1 to N

Table of Contents

Contents are not accessible

Problem Statement

Given an integer N, generate all binary numbers from 1 to N and return them as a list of strings.

Examples

Example 1

Input: N = 2
Output: ["1", "10"]
Explanation: The binary representation of 1 is "1", and the binary representation of 2 is "10".

Example 2

Input: N = 3
Output: ["1", "10", "11"]
Explanation: The binary representation of 1 is "1", the binary representation of 2 is "10", and the binary representation of 3 is "11".

Example 3

Input: N = 5
Output: ["1", "10", "11", "100", "101"]
Explanation: These are the binary representations of the numbers from 1 to 5.

Solution

To solve this problem, we'll use a queue to systematically generate binary numbers. Initially, we enqueue the binary representation of '1'. For each number from 1 to N, we perform the following steps: dequeue the front element of the queue and record it as the current binary number. Then, we generate the next two binary numbers by appending '0' and '1' to the current number and enqueue these new numbers. This process continues until we have generated all binary numbers up to N. This method efficiently leverages the queue's FIFO (First In First Out) nature to build upon previous binary numbers, ensuring a systematic and orderly generation of binary representations.

Step-by-Step Algorithm

Initialize a Queue: Create a queue data structure which will be used to hold binary numbers in string format.
Start with '1': Enqueue the binary representation of the first number, which is '1'.
Iterate up to N: Set up a loop that runs from 1 to N. This loop controls how many binary numbers you need to generate.
Dequeue and Output: In each iteration of the loop, dequeue an element from the front of the queue. This element is the binary representation of the current number. Store or print this number as part of the solution.
Generate Next Binary Numbers:
- Take the dequeued binary number and append '0' to it, forming the next binary number. Enqueue this new number back into the queue.
- Repeat the above step, but this time append '1' instead of '0'.
Repeat the Process: Continue this process until the loop completes its iteration up to N. Each iteration generates the next set of binary numbers based on the current numbers in the queue.

Algorithm Walkthrough

1 of 12

Code

Here is how we can implement this algorithm:

Python3

. . . .

Complexity Analysis

Time Complexity

Queue operations: The algorithm uses a queue to generate binary numbers in order. For each of the n numbers, it performs the following operations:
- Dequeue operation: This is done once per number and takes $O(1)$ time.
- Enqueue two new numbers: For each number, two new binary numbers (appending '0' and '1') are generated and enqueued. Each enqueue operation also takes $O(1)$ time.
Since there are n iterations, and each iteration involves constant-time operations for dequeueing and enqueueing, the overall time complexity is $O(n)$ .

Overall time complexity: $O(n)$ .

Space Complexity

Result array: The result array stores the n binary numbers, which takes $O(n)$ space.
Queue space: The queue stores intermediate binary numbers. At any point in time, the queue holds at most two binary numbers for each element processed. This means that the maximum number of elements in the queue is proportional to n, so the queue requires $O(n)$ space.

Overall space complexity: $O(n)$ .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible