Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Generate Binary Numbers from 1 to N

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

.....

.....

.....

Like the course? Get enrolled and start learning!
Leopoldo Hernandez

Leopoldo Hernandez

· 2 years ago

The solution is optimized for time for fails a tad with space. If you notice, no matter how what number we pass, we will always have twice as many numbers in the queue because of the way we are storing this. we can actively guard against this with some conditional clauses.

Show 3 replies
Steve Ochoa

Steve Ochoa

· 2 years ago

You don't need to put(s2) as it is never looked at. We only ever peek once per iteration (only access index of -1 once).

N

n.place

· a year ago

The key to understanding this is

  1. understanding BFS (breadth-first search)

  2. understanding that binary, or any place system numbers, can be represented in a tree. For binary, each place represents two values, which can be represented as binary nodes in a tree:

                    "1"

             /           \

     "10"                 "11"

   /          \            /            \

    "100". "101". "110" "111

each node in the tree can make two new numbers, by adding a 0 and a 1, as shown above.

The BFS algorithm is


function bfs(root) {

    if (!root) return;



    const queue = new Queue();

    queue.enqueue(root);



    while (!queue.isEmpty()) {

      const node = queue.dequeue();



      // Process current node

      consol
T

traviswlilleberg

· 9 months ago

Maybe I'm missing something but I don't see any reason to declare and use the s2 variable in the JS solution:

       let s2 = s1;               // Copy the dequeued binary number.
        queue.enqueue(s1 + "0");   // Enqueue the first generated binary number by adding "0".
        queue.enqueue(s2 + "1");   // Enqueue the second generated binary number by adding "1".

can be:

        queue.enqueue(s1 + "0");   // Enqueue the first generated binary number by adding "0".
        queue.enqueue(s1 + "1");   // Enqueue the second generated binary number by adding "1".