Digit by digit java solution

  • 0

    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.

Log in to reply

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