K-th Smallest in Lexicographical Order

Intuition

Solution

class Solution:
    def _cal_steps(self, n, n1, n2):
        steps = 0
        while n1 <= n:
            steps += min(n + 1, n2) - n1
            n1 *= 10
            n2 *= 10
        return steps

    def findKthNumber(self, n: int, k: int) -> int:
        current = 1
        k = k - 1
        while k > 0:
            steps = self._cal_steps(n, current, current + 1)
            if steps <= k:
                current += 1
                k -= steps
            else:
                current *= 10
                k -= 1
        return current