K-th Smallest in Lexicographical Order

Leetcode Problem:

• K-th Smallest in Lexicographical Order

Summary

• Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].

Approach

• The solution uses a binary search approach to find the kth lexicographically smallest number
• It first calculates the number of numbers less than or equal to n that can be formed by appending a digit from 1 to 9 to the current number
• Then it recursively finds the kth lexicographically smallest number by finding the kth number that can be formed by appending a digit from 1 to 9 to the current number.

Complexity

• O(log(n))

Explain

• The solution consists of two main functions: findKthNumber and findKthNumber
• The findKthNumber function takes an integer n and an integer k as input and returns the kth lexicographically smallest number
• The findKthNumber function uses a binary search approach to find the kth lexicographically smallest number
• It first calculates the number of numbers less than or equal to n that can be formed by appending a digit from 1 to 9 to the current number
• Then it recursively finds the kth lexicographically smallest number by finding the kth number that can be formed by appending a digit from 1 to 9 to the current number
• The second findKthNumber function is used to calculate the number of numbers less than or equal to n that can be formed by appending a digit from 1 to 9 to the current number.

Solution Code:

class Solution {
public:
    int findKthNumber(int n, int k) {
        int result = 1;
        while (k > 1) {
            int count = findKthNumber(result, result + 1, n);
            if (count < k) {
                result++;
                k -= count;
            } else {
                result *= 10;
                k--;
            }
        }
        return result;
    }
    int findKthNumber(long p, long q, long n) {
        int result = 0;
        while (p <= n) {
            result += min(q, n + 1) - p;
            p *= 10;
            q *= 10;
        }
        return result;
    }
};