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

• 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];
}
};
``````

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