Quick Overview

Binary strings are listed shortest first and in lexicographic order within each length, starting from the empty string. Return the n-th string for n up to a quadrillion. The problem tests counting strings by length, mapping an index to a string, and recognizing the structure of the ordering.

Find the n-th binary string ordered by length, then lexicographically

Company: Quora

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

List every string made of the characters `0` and `1`, shortest first, with strings of the same length in lexicographic order: the empty string, `0`, `1`, `00`, `01`, `10`, `11`, `000`, and so on. Return the n-th string in this list. ### Function Signature ```python def nth_binary_string(n: int) -> str: ``` ### Rules - Positions are 1-indexed: `n = 1` is the empty string `""`, `n = 2` is `"0"`, and `n = 3` is `"1"`. - Strings of equal length are ordered lexicographically, with `"0"` before `"1"`. ### Constraints - `1 <= n <= 10^15` - `n` can exceed the 32-bit integer range; use 64-bit integers in languages with fixed-width types. ### Examples **Example 1** ```text Input: n = 1 Output: "" ``` The list starts with the empty string. **Example 2** ```text Input: n = 6 Output: "10" ``` The list begins `""`, `"0"`, `"1"`, `"00"`, `"01"`, `"10"`, so the sixth string is `"10"`. **Example 3** ```text Input: n = 12 Output: "100" ``` After `"11"` at position 7, the strings of length 3 begin: `"000"` at 8, `"001"` at 9, `"010"` at 10, `"011"` at 11 and `"100"` at 12.

Overview: Binary strings are listed shortest first and in lexicographic order within each length, starting from the empty string. Return the n-th string for n up to a quadrillion. The problem tests counting strings by length, mapping an index to a string, and recognizing the structure of the ordering.

Read the full Quora Software Engineer interview experience this question came from

Consider the list of every string made of the characters `0` and `1`, ordered shortest first, with strings of the same length in lexicographic order: the empty string, `0`, `1`, `00`, `01`, `10`, `11`, `000`, `001`, and so on. Given an integer `n`, return the `n`-th string in this list. Implement `nth_binary_string(n)`, which returns that string (the empty string when `n = 1`). ### Rules - Positions are 1-indexed: `n = 1` is the empty string `""`, `n = 2` is `"0"`, and `n = 3` is `"1"`. - Strings of equal length are ordered lexicographically, with `"0"` before `"1"`. ### Constraints - `1 <= n <= 10^15` - `n` can exceed the 32-bit integer range (2^31 - 1); use 64-bit integers in languages with fixed-width types (`long` in Java, `long long` in C++). ### Examples **Example 1** ```text Input: n = 6 Output: "10" ``` The list begins `""`, `"0"`, `"1"`, `"00"`, `"01"`, `"10"`, so the sixth string is `"10"`. **Example 2** ```text Input: n = 12 Output: "100" ``` After `"11"` at position 7, the strings of length 3 begin: `"000"` at 8, `"001"` at 9, `"010"` at 10, `"011"` at 11 and `"100"` at 12.

Constraints

  • 1 <= n <= 10^15
  • n can exceed the 32-bit integer range; use 64-bit integers in languages with fixed-width types (long in Java, long long in C++).

Examples

Input: (1,)

Expected Output: ''

Explanation: Minimum valid n (source example 1): position 1 is the empty string.

Input: (2,)

Expected Output: '0'

Explanation: First single-character string; off-by-one check on the 1-indexed start.

Hints

  1. Count how many strings of each length exist, and work out the position at which the strings of a given length begin.
  2. For two strings of the same length made of 0 and 1, how does their lexicographic order relate to their values read as binary numbers?
  3. Check your idea against the 1-indexed start: n = 1 must give the empty string, n = 2 gives "0" and n = 3 gives "1".

Loading coding console...

Show the approach

Approach

There are exactly 2^k binary strings of length k, so all strings shorter than k fill 1 + 2 + ... + 2^(k-1) = 2^k - 1 positions, and the strings of length k occupy positions 2^k through 2^(k+1) - 1. Within one length, lexicographic order over {0, 1} matches numeric order when each string is read as a k-bit binary number with its leading zeros, so the string at position n is the k-bit binary form (leading zeros kept) of the offset n - 2^k. Because 2^k <= n < 2^(k+1), n has exactly k + 1 bits and its top bit is the 2^k bit, so subtracting 2^k removes exactly that bit: the answer is the binary representation of n with its leading 1 dropped. The reference emits bits from the least significant end while the remaining value is greater than 1 (the final 1 is the dropped leading bit), then reverses them. Invariant: after i steps the emitted characters are the i lowest bits of n and the remaining value is n shifted right by i. Edge cases: n = 1 gives the empty string because the loop never runs; a power of two gives all zeros (first string of its length) and 2^(k+1) - 1 gives all ones (last string of its length). n can reach 10^15, beyond 32-bit range, so Java uses long and C++ long long; the answer has at most 49 characters.

Time complexity:
O(log n)
Space complexity:
O(log n)