It's a denary tree


  • 4

    A naive solution is pre-order traversal of the tree. We can do better by skipping over a sub-tree if the k is larger than the number of nodes in that sub-tree + current index.

    Function count does the part of counting number of nodes in a sub-tree given prefix of number in lexicographical order.

    public class Solution {
        int index = 0;
        int ans = 0;
        public int findKthNumber(int n, int k) {
            for(int i=1;i<=9;i++) {
                int c = count(n, i, "");
                if(k>c+index) {
                    index+=c;
                    continue;
                }
                if(helper(n, k, ""+i)) break;
            }
            return ans;
        }
        public boolean helper(int n, int k, String cur) {
            index++;
            if(index==k) {
                ans = Integer.valueOf(cur);
                return true;
            }
            for(int i=0; i<=9; i++) {
                int c = count(n, i, cur);
                if(k>c+index) {
                    index+=c;
                    continue;
                }
                if(Integer.valueOf(cur+i)<=n) if(helper(n, k, cur+i)) return true;
            }
            return false;
        }
        public int count(int n, int i, String prefix) {
            long cur = Long.valueOf(prefix+i);
            int ans = 0;
            int number = 1;
            while(cur<=n) {
                ans += number;
                cur *= 10;
                number *= 10;
            }
            if(n<(cur/10+number/10-1)) ans -= cur/10+number/10-1-n;
            return ans;
        }
    }
    

Log in to reply
 

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