K-th Smallest in Lexicographical Order

Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.

Note: 1 ≤ k ≤ n ≤ 109.

Example:

Input:
n: 13   k: 2

Output:
10

Explanation:
The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

Such an "exciting" problem. At first I thought I can use the same approach as lexicographical numbers, but it looks like keep using recursion will lead stack overflow problem. So we have to calculate how many numbers there are before 10. The approach follows this solution, which treats the numbers as a denary prefix tree:



                               1                               2                ...      9
        /   /  \       \          /  /   \       \     /    /   \        \      /    |   |        \
    10           11        12      ...   19     20 21 22 ... 29 90 91 92 ... 99
   /   \            /           |          /      \                                                 |
100 101 ... 110 ... 120 ... 190 ... 199                   ......                999



The tree doesn't look very nice, but you get what I mean. So for each number, we first calculate how many children it has (that are less than n) until we find the node will the kth number lies there. Now for each children of the node, we calculate how many children it has (that are less than n) until we find the children node, then recursively get the result. I tried to avoid using String as the original solution mentioned, not quite successful...

    private int rstIndex = 0;
    public int findKthNumber(int n, int k) {
        if (n < k) {
            return -1;
        }
        int index = 0;
        int ans = -1;
        for (int i = 1; i <= 9; i++) {
            int nextIndex = getIndex(i, n);
            if (index + nextIndex < k) {
                index += nextIndex;
            } else {
                rstIndex = index;
                ans = getAns("" + i, n, k);
                break;
            }
        }
        return ans;
    }

    private int getIndex(long curr, int n) {
        int rst = 0;
        int num = 1;
        while (curr <= n) {
            rst += num;
            curr *= 10;
            num *= 10; //10~19, 100 ~199 ...

        }
        curr /= 10;
        num /= 10;
        if (n < curr + num - 1) {
            rst -= curr + num - 1 - n;
        }
        return rst;
    }

    private int getAns(String curr, int n, int k) {
        rstIndex++;
        if (rstIndex == k) {
            return Integer.valueOf(curr);
        }
        int ans = -1;

        for (int i = 0; i <= 9; i++) {
            int nextIndex = getIndex(Long.valueOf(curr + i), n);
            if (rstIndex + nextIndex < k) {
                rstIndex += nextIndex;
            } else {
                ans = getAns(curr + i, n, k);
                break;
            }
        }
        return ans;
    }