C++ 3ms solution using stack


  • 0
    B

    Test the prefix of the answer each time. If the total number of current prefix is less than k, test the next prefix with current prefix +1, otherwise test longer prefix with current prefix * 10

    class Solution {
    public:
        int findKthNumber(int n, int k) {
            stack<int> stk;
            stk.push(1);
            
            while(k){
                if(k == 1) return stk.top();
                long long top = stk.top(), x = top;
                stk.pop();
                long long sum = 0, mask = 1;
                
                while(top <= n){
                    if(top + mask - 1 <= n) sum += mask;
                    else sum += n - top + 1;
                    top *= 10;
                    mask *= 10;
                }
                
                if(k > sum){
                    k -= sum;
                    stk.push(x+1);
                }else{
                    k --;
                    stk.push(x*10);
                }
            }
            return stk.top();
        }
    };

  • 0
    L

    Great solution. Thanks a lot. Actually, stack is not necessary. One variable is enough.

    class Solution {
    public:
        int findKthNumber(int n, int k) {
            int cur = 1;
            while(k > 0) {
                if(1 == k) return cur;
                int sum = calc(n, cur);
                if(k > sum) {
                    k -= sum;
                    cur = cur + 1;
                }
                else {
                    k --;
                    cur = cur * 10;
                }
            }
            return cur;
        }
        int calc(int n, int64_t x) {
            int ans = 0, t = 1;
            while(x <= n) {
                if(x + t - 1 <= n) ans += t;
                else ans += n - x + 1;
                x *= 10;
                t *= 10;
            }
            return ans;
        }
    };
    

Log in to reply
 

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