Find the k-th smallest integer in lexicographical order among all numbers from 1 to n.
Given two integers n and k, consider the numbers from 1 to n sorted as strings in dictionary order. Return the number that appears in position k in that ordering.
For example, for n = 13, the lexicographical order is 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9. The 5th number is 13.
Your task is to determine the k-th smallest number without explicitly generating and sorting all numbers from 1 to n when n is large.
Input Format
- Two integers
nandk. 1 <= k <= n.
Output Format
- Return a single integer: the
k-th number in lexicographical order from1ton.
Constraints
1 <= k <= n.nmay be large enough that enumerating all numbers is not efficient.- Lexicographical order is based on the decimal string representation of numbers.
Example 1
Input
n = 13, k = 5
Output
13
Explanation
The lexicographical ordering is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the 5th element is 13.
Example 2
Input
n = 100, k = 10
Output
17
Explanation
The ordering begins [1, 10, 100, 11, 12, 13, 14, 15, 16, 17, ...], so the 10th element is 17.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.