Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].
1-n 's lexicographically results?
1 10 100 100 1000 ... 100001 100002
i don't know... we need to padding zero, then we can add it reversely?
I saw a dfs solution. It means we keep timing 10 and in the end we go back and add 1; it will tle...
let me see the std. the std told me it's a denary tree. Oh, all number exist first is starting with the one, and after that with number 2. It means we can take 1 as the root and expand it.
so the accelerate part is here: for the number 1 - 2, how to know whether the number k in it or not. So we must compute the number of lexicographically number between 1 and 2. we need to do 1 + 10 - 20 + 100 - 200 + ... so it basically unitl we add it to smaller than n.
if the step <= k; we let cur + 1 directly. We do not need to compute these number anymore!
Also, if the step is in the k. We need to let the cur*= 10; for example, 10, 11 we have 110 - 100; so if it in the 110, we have 110 now, and so the step between 110 and 111 only one step, we will let 110 ++; that's really interesting.
AC! how clevey solution!