# Java DFS Solution

• ``````public int findKthNumber(int n, int k) {
Deque<Integer> stack = new ArrayDeque<>();
int count=0;
for(int i=1;i<10;i++) {
stack.push(i);
while(!stack.isEmpty()) {
int current = stack.pop();
if(k==++count) return current;
int countInSubtree = count(n,current);
if(countInSubtree+count<k) {
count=countInSubtree+count-1;
} else {
for(int j=9;j>=0;j--) {
int nextVal = Integer.parseInt(""+current+j);
if(nextVal<=n) {
stack.push(nextVal);
}
}
}
}
}
return -1;
}

public int count(int n, long val) {
int ans = 0;
int number = 1;
while(val<=n) {
ans += number;
val *= 10;
number *= 10;
}
if(n<(val/10+number/10-1)) ans -= val/10+number/10-1-n;
return ans;
}
``````

• Same here. But I didn't use the count method so I got TLE. I tried my best to learn the count method but I failed. Could you explain a bit more on the count method? Thanks.

• Nice solution. But you need to consider the Integer overflow problem. change following block of your code

``````for(int j=9;j>=0;j--) {
int nextVal = Integer.parseInt(""+current+j);
if(nextVal<=n) {
stack.push(nextVal);
}
}
``````

to

``````for(int j=9;j>=0;j--) {
if (Long.parseLong(""+current+j) <= (long)n) {
int nextVal = Integer.parseInt(""+current+j);
stack.push(nextVal);
}
}
``````

could pass the case
681692778
351251360

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