同: https://www.acwing.com/solution/LeetCode/content/6248/
/*
数据集为1e9, 直接构造的话每次k--, 复杂度为O(k), 耗时太高
所以需要按位构造, 10进制下按位构造复杂读为log10(k) , 计算量很小


1. 划分结果集:  计算以 prefix 开头 && <= n 的数组有多少个, 记为size
1.1 如果 k == 1 , prefix 为最终结果
1.2 如果 k <= size, 那么必定在 以当前prefix 开头, 且不等于prefix 的范围内, k--, prefix*=10
1.3 如果 k > size , 那必以 >prefix 开头的数字中,  k-=size, prefix++

2. 计算以perfix 开头&& <= n 共有多少个数: 划分为 最高数位 和 剩余数位
2.1 最高数位: 1 位 : 1 + 0
             2位 : 1 + 10 (0~9)
             3 位: 1 + 100 (0~00)

2.2 剩余数位: min(全补完, 补完差值 )  = min(remain, diff)
                1-23,   1-13
2.3 prefix*10 可能爆int, 要转为long


3.3 两个函数的复杂度都为 log10(n) , 即为 O( log10(n) ^ 2  )
*/

class Solution {
    public int findKthNumber(int n, int k) {
        int prefix = 1;
        while (k != 1){
            int size = getPrefixSize(prefix*1L, n);
            if (k <= size){
                k--;
                prefix *= 10;
            } else {
                k-= size;
                prefix++;
            }
        }
        return prefix;
    }

    public int getPrefixSize(long prefix, int n){
        int total = 0;
        long  remain = 1;

        while (prefix * 10 <= n){
            total += remain;
            prefix *= 10;
            remain *= 10;
        }

        if (prefix <= n) total += Math.min(remain, n-prefix+1);

        return total;
    }
}