So, we arrange numbers in a tree. If we know the size (the number of nodes) of every subtree, we can navigate the tree to find the digits of the target number.

Suppose `n=4xx`

. It's easy to see that any subtree rooted at `1,2,3`

has a size of `111`

, and any subtree rooted at `5,6,7,8,9`

has a size of `11`

. -- What about the subtree at `4`

?

Since the size of all subtrees at this level is `n`

, the size of subtree rooted at `4`

is `n-3*111-5*11`

.

Given any `k`

, we can easily find the first digit of the solution. We then adjust `n`

and `k`

, and descend to a lower level to find other digits.