02 Aug 2024•Python•Unknown

Kth Smallest In Lexicographical Order

notes and solution files for kth smallest in lexicographical order.

this entry collects the solution files i have for kth smallest in lexicographical order. i may expand it with a fuller write-up later, but the implementation files are already here.

available solution files

Python kth-smallest-in-lexicographical-order/solution.py

Solution files

Python•kth-smallest-in-lexicographical-order/solution.py

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def dfs(curr: int, k: int) -> int:
            if k == class="syntax-number">0:
                return curr

            next_count = self.count_next(curr, n)
            if k <= next_count:
                return dfs(curr * class="syntax-number">10, k - class="syntax-number">1)
            else:
                return dfs(curr + class="syntax-number">1, k - next_count)

        return dfs(class="syntax-number">1, k - class="syntax-number">1)

    def count_next(self, curr: int, n: int) -> int:
        count = class="syntax-number">0
        next_val = curr + class="syntax-number">1
        while curr <= n:
            count += min(n + class="syntax-number">1, next_val) - curr
            curr *= class="syntax-number">10
            next_val *= class="syntax-number">10
        return count

solution = Solution()
print(solution.findKthNumber(class="syntax-number">13, class="syntax-number">2))
print(solution.findKthNumber(class="syntax-number">1, class="syntax-number">1))