- get the smallest m with the same number of digits as n, ps: n=356, m=100; n=35000, m=10000
- from m to n, count x (in [m,n]) and when x has a '0' ending, insert y=x/10 before x
- if y still ends with 0, continue inserting action
- repeat [n/10+1,m-1] with step 2 and 3

```
public class Solution {
public int findKthNumber(int n, int k) {
int m = 1, tmp=n/10;
while (tmp>0) {
tmp /= 10;
m *= 10;
}
int firstPartNumber = count(m,n,m);
if (k<=firstPartNumber) return findKthNumber(m,n,m,k);
if (k<=n) return findKthNumber(n/10+1,m-1,m/10,k-firstPartNumber);
return 0;
}
public int count(int start, int end, int flag) {
// assume start and end has same amount of digits, flag represents the smallest number with the same length of digits, such as 10,100,1000,...
int result = 0;
while (flag>0) {
result += (end/flag-start/flag+((start%flag==0)?1:0));
flag /= 10;
}
return result;
}
public int findKthNumber(int start, int end, int flag, int k) {
int left = start, right = end;
// b-search
while (left<=right) {
int mid = (left+right)/2;
int x = count(start,mid,flag);
if (x==k) return mid;
if (x<k)
left=mid+1;
else
right=mid-1;
}
int t = right+1;
int zeroToBedeleted = count(start,t,flag)-k;
for (int i=0; i<zeroToBedeleted; i++)
t /= 10;
return t;
}
}
```