K-th Smallest in Lexicographical Order

Problem Statement

In this problem, you are provided with two integers, n and k. You are required to determine the kth lexicographically smallest integer within the inclusive range from 1 to n. Lexicographically order treats numbers as though they are words in a dictionary where digits are compared like characters. For instance, 11 comes before 2 because 1 is less than 2 when viewed as a string, even though numerically, 2 is smaller than 11.

Examples

Example 1

Input:

n = 13, k = 2

Output:

10

Explanation:

The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

Example 2

Input:

n = 1, k = 1

Output:

1

Constraints

• 1 <= k <= n <= 109

Approach and Intuition

To find the kth lexicographically smallest integer in a given range [1, n], our approach revolves around understanding the lexicographical order and efficiently navigating through numbers to find our desired position without generating the entire sequence. This requires both intuition about string comparison and strategic counting:

1. First, understand the nature of lexicographical order vs numerical order:

   • Lexicographical order means the numbers are ordered as if they were strings or words.
   • Thus, '10' is less than '2' because '1' comes before '2' when viewing the characters from left to right.

2. Based on the example calculations:

   • In Example 1, with n = 13, the sequence in lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]. When examining this order, we notice that all numbers starting with '1' appear before those starting with '2'. Here, the second smallest number is '10'.
   • In Example 2, with n = 1, the sequence is simply [1], as it's the only number in the range.

3. Therefore, a step-by-step breakdown can be:

   • Start with the lowest number (1).
   • Incrementally explore the next possible number sequences by considering numbers as strings — append the next possible digit and check whether this still falls within the range and meets the kth requirement.
   • For large values of n, optimizing the search using a tree or graph traversal can significantly reduce redundant checks. This might involve skipping over large sections of the number space that fall lexicographically beyond our kth value.

Through understanding lexicographical ordering and applying methods of efficient searching and skipping of numbers, this problem, despite its simplicity in constraints, poses an interesting challenge in the design of algorithms to meet the requirements of both correctness and efficiency.

Solutions

class Solution {
public:
    int findKthSmallest(int n, int k) {
        int current = 1;
        k--;
    
        while (k > 0) {
            int steps = calculateSteps(n, current, current + 1);
            if (steps <= k) {
                current++;
                k -= steps;
            } else {
                current *= 10;
                k--;
            }
        }
    
        return current;
    }
    
private:
    int calculateSteps(int n, long start, long next) {
        int steps = 0;
        while (start <= n) {
            steps += min((long)(n + 1), next) - start;
            start *= 10;
            next *= 10;
        }
        return steps;
    }
};