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$

This problem aims to find the $k^{th}$ smallest number in the lexicographical (dictionary) order from $1$ to n. Instead of generating and sorting all numbers from $1$ to n, which would be too slow for large n, let’s take a smarter route by imagining these numbers arranged in a trie. Each node represents a number in a trie, and its children are formed by adding more digits to the end. For example, the root has children $1$ to $9$, and node $1$ has children $10$ to $19$, and so on.

In this solution, we use some math to traverse the trie until we reach the $k^{th}$ smallest number lexicographically. We start with the number $1$ (the first child of the root), which is our current prefix. We aim to find the $k^{th}$ number, so we reduce k by $1$ because we’re already at the first number. Then we begin navigating the trie. We calculate how ...