why TLE on submission, but correct result run code?


  • 0
    W
    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;
        }
    }
    

  • 0
    W

    @1337c0d3r this case
    681692778
    351251360


  • 0

    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 least O(k) time complexity. The trick is that with nand k in hand, you do not have to traverse through all k smallest lexicographical numbers only for the last one. If the problem asks to print all k 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);
          }
        }
    

  • 0
    W

    @zzg_zzm but how to modify with my code? Your posted code is not working


  • 0

    @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 prefix cur. 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;
        }
    

  • 0
    W

    @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.


  • 0

    @weihanzh No problem. I was trying to do the pre-order 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 in O(log N)time; but if asking for printing all values smaller than a target value, then have to do in O(N) time.


Log in to reply
 

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