K Th Smallest In Lexicographical Order - Leetcode Solution

Problem:

Given two integers n and k, find the kth lexicographically smallest integer in the range from 1 to n.

Example: Input: n: 13, k: 2 Output: 10

Explanation: The lexicographically smallest integers in the range from 1 to 13 are: 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, and 9. The 2nd lexicographically smallest integer is 10.

Solution:

To solve this problem, we will use a recursive approach. We will start by finding the number of integers that have the same prefix as the kth lexicographically smallest integer.

1. First, we will calculate the number of integers starting with the prefix '0', '1', '2', and so on up to '1'. We can do this using a for loop that starts from 1 and goes up to 9, since any digit above 9 will require another digit to represent it.

2. Next, we will check whether the number of integers with a particular prefix is greater than or equal to k. If it is, then we can be sure that the kth lexicographically smallest integer starts with the current prefix. If it is less than k, then we move on to the next prefix.

3. Once we have found the prefix, we move one step closer to the kth lexicographically smallest integer by appending the smallest digit possible to the prefix, which is '0'. We then recursively find the kth lexicographically smallest integer in the range from the number obtained by appending 0 to the prefix to the number obtained by appending 9 to the prefix.

4. We repeat this process until we have found the kth lexicographically smallest integer.

Here's the Python code for the solution:

class Solution: def findKthNumber(self, n: int, k: int) -> int: def countPrefixes(n, prefix): count = 0 curr, nxt = prefix, prefix + 1

        while curr <= n:
            count += min(n + 1, nxt) - curr
            curr *= 10
            nxt *= 10
        
        return count
    
    curr = 1
    k -= 1
    
    while k > 0:
        count = countPrefixes(n, curr)
        
        if count <= k:
            curr += 1
            k -= count
        else:
            curr *= 10
            k -= 1
    
    return curr

We start by setting curr to 1 and subtracting 1 from k, since we are indexing from 0 instead of 1. We then enter a while loop that continues until k is 0.

Inside the while loop, we first count the number of integers that start with the prefix curr using the countPrefixes function. If the count is less than or equal to k, then we move on to the next prefix by incrementing curr by 1 and subtracting the count from k. Otherwise, we append a 0 to curr and subtract 1 from k before continuing the loop.

Finally, we return curr which will be the kth lexicographically smallest integer.

1