440. K-th Smallest in Lexicographical Order

Description

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

 

Solutions

Solution: Trie

• Time complexity: O(log²n)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
const findKthNumber = function (n, k) {
  let current = 1;

  const getGap = num => {
    let start = num;
    let end = num + 1;
    let gap = 0;

    while (start <= n) {
      gap += Math.min(n + 1, end) - start;
      start *= 10;
      end *= 10;
    }

    return gap;
  };

  k -= 1;

  while (k) {
    const gap = getGap(current);

    if (gap <= k) {
      current += 1;
      k -= gap;
    } else {
      current *= 10;
      k -= 1;
    }
  }

  return current;
};