Problem

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

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

Solution

Method 1 - Using Prefix navigation

The goal is to find the kth lexicographically smallest integer in the range [1, n]. We can solve this problem efficiently by using a prefix-based approach to navigate through the numbers in a trie-like structure.

  1. Prefix Navigation:
    • Start with the prefix 1.
    • Count the number of numbers with a given prefix.
    • Use this count to navigate closer to the kth number.
  2. Counting Numbers with Prefix: -Count how many numbers are lexicographically between the prefix and the given integer n.
  3. Adjust k and Navigate:
    • Deduct the count of numbers with the current prefix from k.
    • Move to the next prefix if necessary.

Code

Python
class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def count_prefix(curr):
            next, cnt = curr + 1, 0
            while curr <= n:
                cnt += min(n + 1, next) - current
                next, curr = next * 10, curr * 10
            return cnt

        curr = 1
        k -= 1
        while k:
            cnt = count_prefix(curr)
            if k >= cnt:
                k -= cnt
                curr += 1
            else:
                k -= 1
                curr *= 10
        return curr
Java
class Solution {
    private int n;

    public int findKthNumber(int n, int k) {
        this.n = n;
        long curr = 1;
        --k;
        while (k > 0) {
            int cnt = countPrefix(curr);
            if (k >= cnt) {
                k -= cnt;
	            curr++;
            } else {
                k--;
                curr *= 10;
            }
        }
        return (int) curr;
    }

    public int countPrefix(long curr) {
        long next = curr + 1;
        long cnt = 0;
        while (curr <= n) {
            cnt += Math.min(n - curr + 1, next - curr);
            next *= 10;
            curr *= 10;
        }
        return (int) cnt;
    }
}
C++
class Solution {
public:
    int n;

    int findKthNumber(int n, int k) {
        this->n = n;
        --k;
        long long curr = 1;
        while (k) {
            int cnt = count(curr);
            if (k >= cnt) {
                k -= cnt;
                ++curr;
            } else {
                --k;
                curr *= 10;
            }
        }
        return (int) curr;
    }

    int count(long long curr) {
        long long next = curr + 1;
        int cnt = 0;
        while (curr <= n) {
            cnt += min(n - curr + 1, next - curr);
            next *= 10;
            curr *= 10;
        }
        return cnt;
    }
};
Go
func findKthNumber(n int, k int) int {
	count := func(curr int) int {
		next := curr + 1
		cnt := 0
		for curr <= n {
			cnt += min(n-curr+1, next-curr)
			next *= 10
			curr *= 10
		}
		return cnt
	}
	curr := 1
	k--
	for k > 0 {
		cnt := count(curr)
		if k >= cnt {
			k -= cnt
			curr++
		} else {
			k--
			curr *= 10
		}
	}
	return curr
}

…

Complexity

  • Time: O(log n), during each step, we decide the next prefix by investigating digits depths, which could be logarithmic in the number of digits.
  • Space: O(1)