Java 6ms solution, determine digit by digit of the kth number


  • 0
    F

    Basically determine digit by digit for the kth number from most significant digit to least significant digit by computing 2 bounds which divide "1 to n" into 3 regions:

    public class Solution {
        private int k;
        private int n;
        private final static int[] lengths2counts = new int[]{0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111};
    
        private void findKth(int ind, int k, int[] pre){
            if(pre[0] == 0){
                pre[0]= (k - 1)/ lengths2counts[ind] + 1;
                findKth(ind - 1, k - (pre[0] - 1) * lengths2counts[ind], pre);
            }else if(k > 1){
                int curdigit = (k - 2)/ lengths2counts[ind];
                pre[0] = 10 * pre[0] + curdigit;
                findKth(ind - 1, k - 1 - curdigit * lengths2counts[ind], pre);
            }
        }
    
        public int findKthNumber(int n, int k) {
    
            int curdigit = n;
            List<Integer> list = new ArrayList<>();
            while(curdigit != 0){
                list.add(curdigit % 10);
                curdigit /= 10;
            }
    
            int[] res = new int[]{0};
            for(int ind = list.size() - 1; ind >= 0; ind --) {
                curdigit = list.get(ind);
                int lb = (ind == list.size() - 1) ? (lengths2counts[ind + 1] * (curdigit - 1)) : (lengths2counts[ind + 1] * curdigit  + 1) ;//lower bound
                int ub = n - (9 - curdigit) * lengths2counts[ind]; //upper bound
                if (k > ub) {
                    int temp = (k - ub - 1)/ lengths2counts[ind];
                    res[0] = 10 * res[0] + curdigit + temp + 1;
                    findKth(ind - 1, k - ub - temp * lengths2counts[ind], res);
                    break;
                } else if (k <= lb) {
                    findKth(ind + 1, k, res);
                    break;
                }
                res[0] = 10 * res[0] + curdigit;
                n = ub - lb;
                k -= lb;
            }
            return res[0];
        }
    }
    

Log in to reply
 

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