# Solving Leetcode Interviews in Seconds with AI: K-th Smallest in Lexicographical Order


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "440" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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  

	# Explanation
	*   **Lexicographical Tree Traversal:** The core idea is to treat the problem as traversing a 10-ary tree where each node represents a prefix. We navigate this tree to find the kth smallest element.
*   **Calculate Steps:** For each potential prefix, we determine how many numbers fall under that prefix in the lexicographical order.  This involves calculating how many descendants a node has.
*   **Adjust k:** If the number of numbers under a prefix is less than `k`, it means the kth smallest number is not under that prefix. We subtract the number of numbers under the prefix from `k` and move to the next prefix. Otherwise, we move down the tree (multiply the prefix by 10).

*   **Runtime Complexity:** O(log n * log n) - due to the depth of the implicit tree and the calls to the `get_steps` helper function. **Storage Complexity:** O(1) - constant extra space.

	
	# Code
	```python
	def findKthNumber(n: int, k: int) -> int:
    """
    Finds the kth lexicographically smallest integer in the range [1, n].
    """

    def get_steps(curr: int, n: int) -> int:
        """
        Calculates the number of integers between curr and curr + 1 (exclusive)
        in the range [1, n].  This is equivalent to the number of descendants
        of curr in the lexicographical tree.
        """
        steps = 0
        first = curr
        last = curr + 1
        while first <= n:
            steps += min(n + 1, last) - first
            first *= 10
            last *= 10
        return steps

    curr = 1
    k -= 1  # Adjust k to be 0-indexed

    while k > 0:
        steps = get_steps(curr, n)
        if steps <= k:
            k -= steps
            curr += 1
        else:
            curr *= 10
            k -= 1

    return curr
	```