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.
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
Since the size of all subtrees at this level is
n, the size of subtree rooted at
k, we can easily find the first digit of the solution. We then adjust
k, and descend to a lower level to find other digits.