K-th Smallest in Lexicographical Order

How it works

Numbers in lexicographical order form a tree structure where each prefix leads to its extensions. For example, prefix "1" leads to "10", "11", ..., "19", "100", etc. We can count how many numbers exist under any prefix without enumerating them. Starting at "1", we count how many numbers lie in the subtree rooted at the current prefix. If this count is less than or equal to the remaining k, we skip this entire subtree and move to the next sibling. Otherwise, we descend into the subtree by appending a digit.

Steps

1. Define count(cur) to calculate how many numbers in [1, n] have cur as a prefix.
2. Start with cur = 1 and i = 1 (position in lexicographical order).
3. While i < k:
   • Calculate steps = count(cur).
   • If i + steps <= k, move to the next sibling: cur++ and i += steps.
   • Otherwise, descend into children: cur *= 10 and i++.
4. Return cur when i == k.

Complexity

• Time complexity: O((log n) ^ 2)
• Space complexity: O(1)

Things to watch for

Confusing Lexicographical Order with Numerical Order

In lexicographical order, "10" comes before "2" because strings are compared character by character. Treating numbers numerically instead of as strings leads to completely wrong results. The sequence starts 1, 10, 100, ..., 2, 20, ....

Integer Overflow in Prefix Counting

When counting numbers under a prefix, the prefix and its neighbor are multiplied by 10 repeatedly. For large n, these values can exceed 32-bit integer limits. Use 64-bit integers (long in Java, long long in C++) for the counting logic.

Incorrect Step Counting Logic

The count function must include the prefix itself plus all its extensions up to n. The formula min(neighbor, n + 1) - cur counts numbers in the current level. A common error is using n instead of n + 1, which excludes the boundary value.

Off-by-One in Position Tracking

The position variable i starts at 1 (representing we are at number 1). When moving to a child, increment i by 1. When skipping a subtree, increment i by the step count. Confusing these increments places you at the wrong number.

Not Handling Single-Digit to Multi-Digit Transitions

When descending from prefix "1" to "10", you multiply by 10. But if 10 > n, you cannot descend further. The algorithm must handle cases where the current prefix exceeds n after multiplication, which the count function naturally handles by returning 0.

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        cur = 1
        i = 1

        def count(cur):
            res = 0
            nei = cur + 1
            while cur <= n:
                res += min(nei, n + 1) - cur
                cur *= 10
                nei *= 10
            return res

        while i < k:
            steps = count(cur)
            if i + steps <= k:
                cur = cur + 1
                i += steps
            else:
                cur *= 10
                i += 1

        return cur

class Solution {
public:
    int findKthNumber(int n, int k) {
        long long cur = 1;
        long long i = 1;
        while (i < k) {
            long long steps = count(cur, n);
            if (i + steps <= k) {
                cur++;
                i += steps;
            } else {
                cur *= 10;
                i++;
            }
        }
        return (int)cur;
    }

private:
    long long count(long long cur, int n) {
        long long res = 0;
        long long nei = cur + 1;
        while (cur <= n) {
            res += min(nei, (long long)n + 1) - cur;
            cur *= 10;
            nei *= 10;
        }
        return res;
    }
};