0595HardTrie

Manifest Position of a Lot Label

Tracked in this browser only

Trains the technique from

LeetCode 440K-th Smallest in Lexicographical Order

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def find_kth_number(n: int, k: int) -> int:

Java

public int findKthNumber(int n, int k)

The intended approach

Time O((log n)^2): each of at most log n descents does a counting walk of length at most log n.Space O(1) beyond the two integers being tracked.

Appending a digit to a label produces a label that follows it immediately on the manifest, which arranges the labels into a ten-way tree rooted at the nine labels `1` through `9`. Counting how many labels sit at or below a given label is done level by level: at each level the descendants form the contiguous range from `low` to `high`, clipped at `n`, and the next level is reached by `low *= 10` and `high = high * 10 + 9`. Starting from `1`, repeatedly ask how many labels the current label covers: if that many or fewer positions still have to be skipped, skip the whole block and move to the next sibling, otherwise consume one position for the current label and drop to its first child. Both loops run a number of times proportional to the digit count.

Pythonentry point: find_kth_number

def find_kth_number(n, k):
    # O((log n)^2) time, O(1) space. Think of the labels as a ten-way tree: the
    # label 7 is the parent of 70..79, and a label's children always follow it
    # on the manifest. Counting how many labels hang under a given label is a
    # matter of walking one extra digit at a time and taking whole ranges, never
    # visiting labels one by one.
    def under(prefix):
        total = 0
        low = prefix
        high = prefix
        while low <= n:
            top = high if high < n else n
            total += top - low + 1
            low *= 10
            high = high * 10 + 9
        return total

    cur = 1
    remaining = k - 1
    while remaining > 0:
        block = under(cur)
        if block <= remaining:
            # Everything under cur, cur included, sits before the target.
            remaining -= block
            cur += 1
        else:
            # The target is under cur, so step to cur's first child.
            remaining -= 1
            cur *= 10
    return cur

The obvious version

Write out every label from 1 to n as text, sort the whole list of strings, and read off the entry at position k. Only usable for small n, but obviously right.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_find_kth_number(n, k):
    labels = []
    for value in range(1, n + 1):
        labels.append(str(value))
    labels.sort()
    return int(labels[k - 1])

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in