440. K-th Smallest in Lexicographical Order

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

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 01:

class Solution {
 public:
  int findKthNumber(int totalNumbers, int k) {
    long currentNumber = 1;  // The number we are searching for

    // Iterate to find the kth number
    for (int currentPosition = 1; currentPosition < k;) {
      const long gap = calculateGap(currentNumber, currentNumber + 1, totalNumbers);
      
      // Check if the kth number is within this gap
      if (currentPosition + gap <= k) {
        currentPosition += gap;
        ++currentNumber;  // Move to the next number
      } else {
        ++currentPosition;
        currentNumber *= 10;  // Move to the next level in lexicographical order
      }
    }

    return currentNumber;
  }

 private:
  // Function to calculate the gap between two numbers in the lexicographical order
  long calculateGap(long start, long end, long maxNumber) {
    long gap = 0;
    
    // Calculate gap between 'start' and 'end' until 'maxNumber'
    while (start <= maxNumber) {
      gap += min(maxNumber + 1, end) - start;
      start *= 10;
      end *= 10;
    }

    return gap;
  };
};

class Solution:
    def findKthNumber(self, totalNumbers: int, k: int) -> int:
        currentNumber = 1  # The number we are searching for
        currentPosition = 1  # Position counter
        
        # Iterate to find the kth number
        while currentPosition < k:
            gap = self.calculateGap(currentNumber, currentNumber + 1, totalNumbers)
            
            # Check if the kth number is within this gap
            if currentPosition + gap <= k:
                currentPosition += gap
                currentNumber += 1  # Move to the next number
            else:
                currentPosition += 1
                currentNumber *= 10  # Move to the next level in lexicographical order
        
        return currentNumber

    # Function to calculate the gap between two numbers in lexicographical order
    def calculateGap(self, start: int, end: int, maxNumber: int) -> int:
        gap = 0
        
        # Calculate gap between 'start' and 'end' until 'maxNumber'
        while start <= maxNumber:
            gap += min(maxNumber + 1, end) - start
            start *= 10
            end *= 10
        
        return gap

Time Complexity

• Finding the Kth Number:

  The outer loop runs until we reach the kth number. In the worst case, this may involve traversing the levels of the lexicographical tree, which can be approximated as \(O(\log_{10}(k))\) since each step down the tree multiplies the current number by 10.

• Calculating the Gap:

  The calculateGap function iterates while the start number is less than or equal to maxNumber. The number of iterations can be bounded by \(O(\log_{10}(totalNumbers))\) because the start variable grows exponentially (by a factor of 10) until it exceeds maxNumber.

• Overall Time Complexity:

  The total time complexity is \(O(\log_{10}(k) \cdot \log_{10}(totalNumbers))\) due to the nested nature of the loops.

Space Complexity

• Space Usage:

  The algorithm uses a constant amount of extra space for variables like currentNumber, currentPosition, and others. Thus, there is no additional space that grows with input size.

• Overall Space Complexity:

  The overall space complexity is \(O(1)\) because the space used does not depend on the input size.