leetcode-go/hard/440.k-th-smallest-in-lexicographical-order.java

class Solution {
    public int findKthNumber(int n, int k) {
        int cur = 1;
        k--;
        // Ten-ary tree
        while (0 < k) {
            int cnt = 0;
            long lo = cur, hi = cur + 1;
            while (lo <= n) {
                cnt += (int) (Math.min(hi, n + 1) - lo);
                lo *= 10;
                hi *= 10;
            } // Count the number of children level by level
            if (cnt <= k) {
                cur++; // Go to next child
                k -= cnt;
            } else {
                cur *= 10; // Go to next level
                k--;
            }
        }
        return cur;
    }
}