3ms C++ solution


  • 0
    I
    class Solution {
    public:
    
        int bnums[11] = {0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111};
        int dnums[11] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
    
        int findKthNumber(int n, int k) {
            string res;
            find(n, to_string(n), k, res, 1);
            return atoi(res.c_str());
        }
    
        void find(int n, const string &nstr, int k, string &res, int be) {
            int nn = nstr.size();
            vector<int> cnts(10, 0);
    
            int c1 = bnums[nn];
            int c2 = bnums[nn-1] + (n % dnums[nn]) + 1;
            int c3 = bnums[nn-1];
    
            int hdi = nstr[0] - '0';
            for (int i = be; i < hdi; i++) cnts[i] = c1;
            cnts[hdi] = c2;
            for (int i = hdi + 1; i <= 9; i++) cnts[i] = c3;
    
            int cnt = 0;
            for (int i = 0; i <= 9; i++) {
                cnt += cnts[i];
                if (cnt >= k) {
                    res.push_back(i + '0');
                    k -= (cnt - cnts[i]);
                    if (k <= 1) return;
                    if (i < hdi) {
                        find(dnums[nn]- 1, to_string(dnums[nn]- 1), k - 1, res, 0);
                    }
                    else if (i == hdi) {
                        string new_nstr = to_string(n % dnums[nn]);
                        int gg = (nn - 1) - new_nstr.size();
                        new_nstr.insert(0, gg, '0');
                        find(n % dnums[nn], new_nstr, k - 1, res, 0);
                    }
                    else {
                        find(dnums[nn-1] - 1, to_string(dnums[nn-1] - 1), k - 1, res, 0);
                    }
                    break;
                }
            }
        }
    };
    

Log in to reply
 

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