public class Solution {
public int findKthNumber(int n, int k) {
long cur = 1;
if (k == 1) {
return 1;
}
k;
for (int i = 1; i <= n; i++) {
if (cur * 10 <= n) {
cur = cur * 10;
} else if (cur % 10 != 9 && cur + 1 <= n) {
cur++;
} else {
while ((cur / 10) % 10 == 9) {
cur = cur / 10;
}
cur = cur / 10 + 1;
}
if (k == 0) {
return (int)cur;
}
}
return (int)cur;
}
}
why TLE on submission, but correct result run code?



I have similar TLE solution to yours while mine is recursion vs your iteration. The time constraint of this problem is that you cannot iterate over the variable
k
, which gives you at leastO(k)
time complexity. The trick is that withn
andk
in hand, you do not have to traverse through allk
smallest lexicographical numbers only for the last one. If the problem asks to print allk
smallest lexicographical numbers, then it would be reasonable to do the traversal.long counter, res; int findKthNumber(int n, int k) { counter = k+1; res = 0; dfs(0, n); return res; } void dfs(long cur, int n) { if (cur > n) return; if (counter == 0) {res = cur; return;} for (int i = 0; i <= 9; ++i) { long next = 10*cur + i; if (next) dfs(next, n); } }


@weihanzh Sorry for the confusion. The code I posted is the "similar TLE solution to yours while mine is recursion vs your iteration", where both codes have at least
O(k)
time complexity, which is not acceptable by OJ for this problem. I knew this wouldn't work.My point is that by OJ standard for this problem, any pure traversal algorithm wouldn't work. So, just "modifying" your code (or mine) wouldn't solve the issue since we both have a counter in the code which only decrements by one at a time.
There are already optimized solutions posted by others and I picked my favorite to rewrite as following. It counts the entire number of valid values altogether of a common prefixcur
. And this is why the optimized solution runs log^2 time vs ours linear time.int findKthNumber(int n, int k) { int cur = 1; while (k > 1) { int cnt = count(cur, n); if (cnt < k) k = cnt, cur++; else cur *= 10, k; } return cur; } // count number of values <= n with prefix "cur" int count(long cur, int n) { int count = 0; for (long s = cur, e = cur+1; s <= n; s*= 10, e *= 10) { count += min(n+1L, e)  s; } return count; }

@zzg_zzm thank you for your reply. I have figured it out by looking an accepted code posted by others. It jumps some steps instead of only jumping one step.

@weihanzh No problem. I was trying to do the preorder traversal of Trie because I have seen a very similar problem which asks to print all values lexicographically smaller than a given target. But that problem is asking for a stronger output than this problem, so more expensive in time complexity. It is like the "
log
" fashion of binary search: if only asking for some value in a sorted array, should be able to do inO(log N)
time; but if asking for printing all values smaller than a target value, then have to do inO(N)
time.