# Digit by digit java solution

• To start, let's denote the answer as `res`. Without much thinking, we know `res` will always be an integer in the range `[1, n]`, therefore it's possible to obtain its value digit by digit. To implement the idea, here are the two questions you may ask yourself:

1. Should we go from most significant digit (MSD) to least significant digit (LSD) or the other way around?

2. What are the conditions for determining the value of each digit?

For the first question, since the numbers will be arranged in lexicographical order, which means they will be compared from MSD to LSD, going in the same direction will be a wise choice (Otherwise later comparisons may override prior ones).

As to the second one, we can proceed in a "trial and error" fashion since there are at most `10` choices (`0 - 9`) for each digit (note `MSD` cannot be `0`). Okay, which one should go first, `0` or `9`? Remember we were asked to get the `k-th` smallest integer, so obviously we'd like to try from `0` up to `9`.

But how exactly do we choose the value for each digit? The principle is simple: count the total number of integers that have the same prefix as the current value of `res`, yet no more than `n`. For example, if `res = 0`, we count all integers starting with `1` (such as `1`, `10`, `100`,...), then with `2` (such as `2`, `20`, `200`...), then with `3`, ..., up to `9` (`note` if `res = 0`, the digit will be MSD so it cannot be `0`); If `res = 13`, we will count all integers starting with `130` such as `130`, `1300`, `13500`, ..., then with `131` like `131`, `1310`,..., up to `139` (and of course `1390`, ...). For a given `k`, if the total count starting with (`res * 10 + i`), where `0 <= i <= 9`, is no less than `k`, then the next digit of `res` will be set as `i`, i.e., `res = res * 10 + i`. Otherwise subtract that total number from `k` and continue with `i` increased by `1`. Eventually `k` will be reduced to `1` and the corresponding value of `res` will be the `k-th` smallest integer in the lexicographical order.

All right, it looks like we are almost there except for how to count the total number of integers with some given prefix. Here is a quick idea: let the prefix be `res` and initially we have a count of `0`. First add one digit to the end of `res` to form a new integer (the value of the digit can be `0 - 9`) and check if the maximum one (i.e. digit added with value `9`) is no more than `n`. If so, increase count by `10` and continue adding another digit to each of the newly-obtained integers above (from smallest to largest) like doing "DFS", until the integer value exceeds `n`. As you can see, for each digit added, the total count for that particular digit will be ten times as that of the previous one. One tricky case is for some digit it cannot take all values up to `9` as doing so would render the number greater than `n`. In such cases we only count values that make the number no more than `n`.

Let's do an example: let `res = 13`, `n = 1350` and `count = 0`. Adding one digit to `res` and check its maximum value `139 < 1350`, so `count = 10`. Then adding another digit and again check its maximum value `1399 > 1350` so now we only retain those valid counts which are from `1300` up to `1350` so `count = 10 + (1350 - 1300 + 1) = 61`.

Finally here is the java program for this digit by digit solution:

``````public int findKthNumber(int n, int k) {
int res = 0;

do {
res *= 10;
int i = (res == 0 ? 1 : 0);

for (int count; i < 10; i++) {
long base = 1, max = (res + i + 1) * base - 1;
for (count = 0; max <= n; base *= 10, max = (res + i + 1) * base - 1) count += base;
if (n >= (res + i) * base) count += (n - (res + i) * base + 1);
if (k <= count) break;
k -= count;
}

res += i;

} while (k-- > 1);

return res;
}
``````

Some explanation of the program:

1. res is the final result, which is initialized to 0.
2. At the beginning of the do-while loop, we shift res one digit to the left so we can determine the value of its current LSD. Also if res is 0, we are up to find the MSD of the final result so the starting digit value will be 1 instead of 0.
3. We then count the total number of integers starting with (res + i) and determine the digit value i. Here base denotes how many digits have been shifted and max is the maximum value with that many digits shifted (with prefix, of course). After counting the normal cases we then double check the corner cases when some of the digit values do not yield valid counts.
4. We set the corresponding digit value of res and continue until k is 1.

Correct me if I was wrong: time complexity is (logn)^2, which can be analyzed as follows: let T(n) be the original problem. For each digit, the total counts for each value are roughly equal so T(n) will be reduced to T(n/10) in logn time, i.e., T(n) = T(n/10) + O(logn) and by Master's theorem we have T(n) = O((logn)^2).

Advanced perspective: all the numbers can be arranged into a denary tree. The sequence 1, 2, .., n will be the result of level order traversal while the sequence of lexicographical order will be preorder traversal. Of course naive simulation of preorder traversal will result in either TLE or StackOverFlow. The right way is again to count the total number of nodes in the subtrees for each node and choose the proper subtree to continue. Since each subtree is a complete tree, it is possible to obtain its total nodes in time proportional to its height, which is logn time with n the total number of nodes. For more details you can refer to pureklkl's post.

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