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

• 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){
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];
}
}
``````

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