Show problems as
Classic problem #440HardTrie

K-th Smallest in Lexicographical Order

Real-world version: Manifest Position of a Lot Label
Tracked in this browser only
Read K-th Smallest in Lexicographical Order on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A bonded warehouse labels its lots with the whole numbers from 1 up to n. The printed manifest treats each label as a piece of text and puts the labels in dictionary order, comparing one character at a time. Under that ordering the label 10 is printed before the label 2, and 100 is printed before 11.

Given n and a position k, return the label that occupies position k of the manifest. Positions are numbered from 1, so position 1 always holds the label 1.

The warehouse may hold as many as a billion lots, so building the whole manifest is out of the question; the answer must be found without listing the labels one at a time.

Examples

Example 1

Input
n = 725, k = 208
Output
286

Position 208 of the manifest for 725 lots holds the label 286. Exactly 207 of the labels from 1 to 725 come before 286 in dictionary order.

Example 2

Input
n = 46, k = 46
Output
9

With 46 lots the manifest has 46 entries, and its final entry is the label 9, because every other label starts with a smaller character.

Example 3

Input
n = 12, k = 5
Output
2

Exactly four labels precede the label 2 in dictionary order, namely 1 followed by the three labels 10, 11 and 12 that begin with the character 1. That puts the label 2 at position 5.

Constraints

  • 1 <= k <= n <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_kth_number(n: int, k: int) -> int:
Java
public int findKthNumber(int n, int k)

More on the same topics