K-th Smallest in Lexicographical Order

Statement

Given two integers, n and k, return the $k^{th}$ smallest number in the range [1, n] when the numbers are sorted lexicographically.

Note: Lexicographical sorting means ordering numbers like words in a dictionary (alphabetical order)—digit by digit from left to right. For example, the numerical order of 1, 5, and 10 is [1, 5, 10], but their lexicographical order is [1, 10, 5].

Constraints:

• $1 \leq$ k $\leq$ n $\leq 10^9$

Examples