K-th Number in Dictionary Order

Sort the numbers from 1 to n as if they were words in a dictionary, comparing their digits from the left. For n = 13 the order is 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9.

Write kth_number(n, k) that returns the k-th number in that order, counting from 1.

Examples

kth_number(13, 2)     # returns 10
kth_number(13, 6)     # returns 2
kth_number(100, 3)    # returns 100

For n = 100 the order starts 1, 10, 100, 11, 12, ...

Constraints

• 1 <= k <= n <= 10^9
• Making and sorting a billion strings is far too slow and too big.