Hint - size of subtree

  • 1

    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.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.