C++ solution : deduce digit one by one (log(n)), 0~3ms)


  • 0

    The idea is to append digit to the number in form of string.

    There 3 main cases during the deduction; let's take input '334' as an example:

    1. if we choose the first digit as 1 (i.e. "under" the prefix value), then it could be "1", "1X","1XX"; that is, there are in total '111' combinations started with 1.
    2. if we place 3 first (i.e. "exact match the prefix value), then it could be "3","3X","300~334"; that is, we can calculate the regular part "3","3X"(11 numbers in total), and the variable part ("300~334", 35 in total), where the variable part can be calculated with modulo operator on the original input.
    3. Besides the 2 cases above, the last case is "over" the prefix value (for example, "4" and "4X"). You can compare this part to case 1 or 2, and you will see the difference.

    in all cases the total number of the entries started with a certain digit is SUM(10^0,10^1,.....10^x), where x depends on which digit you are trying to figure out. (the number is consecutive '1' if you write it down.) In my implementation, I use a table to represent it.(function 'pow10Sum')

    The code:

    class Solution {
    public:
    
        int findKthNumber(int n, int k) {
            string strN = to_string(n);
            bool isPrefix = true; // initially empty string is a prefix in any case
            int i,j;
            for(i=0, j = strN.size()-1, out=0;i<strN.size() && k;++i,--j) {
                --k; //current prefix occupied a position, too
                if(isPrefix) {
                    char startDigit = '0' + max(0,1-i);
                    int under, exact, over;
                    under = (strN[i] - startDigit) * pow10Sum(j);
                    if(under > k) {
                        strN[i] = startDigit + k/pow10Sum(j);
                        k   %= pow10Sum(j);
                        isPrefix = false;
                    } else {
                        k -= under;
                        exact = pow10Sum(j-1) + n % pow10(j) +1;
                        if(exact > k) {
                            strN[i] = strN[i];
                        } else {
                            --j;
                            k -= exact;
                            strN[i] = strN[i]+1 + k/pow10Sum(j);
                            k   %= pow10Sum(j);
                            isPrefix = false;
                        }
                    }
                } else {
                    strN[i] = '0' + k/pow10Sum(j);
                    k   %= pow10Sum(j); 
                }
            }
            strN.resize(i);
            return atoi(strN.data());
        }
        // return 10 ^ exp
        int pow10(int exp) {
            const static int arr[] {
                1,
                10,
                100,
                1000,
                10000,
                100000,
                1000000,
                10000000,
                100000000,
                1000000000,
            };
            return arr[exp];
        }
        // return pow10(0) + pow10(1) + ....pow10(exp)
        int pow10Sum(int exp) {
            const static int arr[] {
                1,
                11,
                111,
                1111,
                11111,
                111111,
                1111111,
                11111111,
                111111111,
                1111111111,
            };
            return arr[exp];
        }
    };
    

Log in to reply
 

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