Generate Binary Numbers From 1 to n Using a Queue

Given a positive integer n, return the binary representations of every number from 1 to n, in order, as strings.

Example 1

Input:  n = 5
Output: ["1", "10", "11", "100", "101"]

Example 2

Input:  n = 1
Output: ["1"]

Brute force: convert each number separately

To convert x to binary, divide it by 2 repeatedly. The remainders are the bits, least significant first, so reverse them at the end. A StringBuilder is a mutable string buffer: append adds a character and reverse reverses the buffer in place.

6 / 2 = 3 remainder 0
3 / 2 = 1 remainder 1
1 / 2 = 0 remainder 1      bits read backwards: "110"

import java.util.ArrayList;
import java.util.List;

public class Main {
    static String toBinary(int x) {
        StringBuilder bits = new StringBuilder();
        while (x > 0) {
            bits.append(x % 2 == 1 ? '1' : '0');
            x /= 2;
        }
        return bits.reverse().toString();
    }

    static List<String> binaryNumbers(int n) {
        List<String> result = new ArrayList<>();
        for (int x = 1; x <= n; x++) {
            result.add(toBinary(x));
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(binaryNumbers(5));
        System.out.println(toBinary(6));
    }
}

[1, 10, 11, 100, 101]
110

Time: O(n log n): each number has about log₂ n bits. Space: O(n log n) for the output strings.

In real code, Integer.toBinaryString(x) formats a number in binary. The lists below print in the form [1, 10, 11], without quotes around the strings.

Optimal: generate them in order with a queue

Every binary number s gives the next two binary numbers of the next length: s + "0" and s + "1". Starting from "1", this forms a binary tree, and reading the tree level by level lists the numbers in increasing order:

graph TB
    n1["1"] --> n10["10"]
    n1 --> n11["11"]
    n10 --> n100["100"]
    n10 --> n101["101"]
    n11 --> n110["110"]
    n11 --> n111["111"]

A queue produces exactly that level-by-level order. ArrayDeque is Java's resizable array queue: add appends at the back and remove takes from the front, throwing NoSuchElementException when the queue is empty.

1. Start with "1" in the queue.
2. Take s from the front and add it to the result.
3. Push s + "0" and s + "1" to the back.
4. Stop after n results.

Walkthrough with n = 5:

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class Main {
    static List<String> binaryNumbers(int n) {
        List<String> result = new ArrayList<>();
        Queue<String> queue = new ArrayDeque<>();
        queue.add("1");
        while (result.size() < n) {
            String s = queue.remove(); // never empty: every removal adds two
            queue.add(s + "0");
            queue.add(s + "1");
            result.add(s);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(binaryNumbers(5));
        System.out.println(binaryNumbers(10));
        System.out.println(binaryNumbers(0));
    }
}

[1, 10, 11, 100, 101]
[1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010]
[]

Time: O(n log n), since each new string copies up to log₂ n characters. Space: O(n log n). The queue holds at most about n strings of O(log n) characters.

Both approaches have the same complexity. The queue approach is the one the problem asks for, and it is the same loop as breadth-first search: take an item from the front, add its children to the back.

queue.remove() is safe here: the queue starts with one element, and every iteration removes one and adds two, so it is never empty inside the loop.

Edge cases

• n = 0: the loop does not run, and the result is empty.
• Large n: the queue holds more strings than needed near the end (up to about n extra). To avoid that, stop pushing children once result.size() + queue.size() >= n.