Sponsored
Sponsored
This approach involves systematically traversing a conceptual lexicographical tree. Each integer can be considered a node, with its child nodes being its successors in a lexicographical sense. By counting numbers in subtrees, we can determine where the k-th smallest number lies without generating the entire lexicographical list.
Time Complexity: O(log(n)^2), as we are traversing a tree where we potentially explore and count nodes at each level.
Space Complexity: O(1), since we are not using any additional data structures.
1class Solution:
2 def findKthNumber(self, n: int, k: int) -> int:
3 def count_steps(n, curr, next):
4 steps = 0
5 while curr <= n:
6 steps += min(n + 1, next) - curr
7 curr *= 10
8 next *= 10
9 return steps
10
11 curr = 1
12 k -= 1
13 while k > 0:
14 steps = count_steps(n, curr, curr + 1)
15 if steps <= k:
16 curr += 1
17 k -= steps
18 else:
19 curr *= 10
20 k -= 1
21 return curr
22
23# Example usage
24sol = Solution()
25print(sol.findKthNumber(13, 2)) # Output: 10The Python solution utilizes a helper function count_steps to evaluate numbers between nodes. The main loop in findKthNumber decides whether to go deeper in the tree or move laterally based on the available steps count to reach the k-th number efficiently.
This approach leverages binary search combined with a counting function to directly determine the k-th lexicographical number. Instead of constructing the list, we estimate the position of the k-th number by adjusting potential candidates using the count of valid numbers below a mid-point candidate.
Time Complexity: O(log(n)^2), where binary search narrows down potential candidates.
Space Complexity: O(1), minimal variable storage is employed.
class Solution {
public int FindKthNumber(int n, int k) {
int low = 1, high = n;
while (low < high) {
int mid = low + (high - low) / 2;
if (CountBelow(n, mid) < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
private long CountBelow(long n, long prefix) {
long count = 0;
long factor = 1;
while (prefix <= n) {
count += Math.Min(factor, n - prefix + 1);
prefix *= 10;
factor *= 10;
}
return count;
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.FindKthNumber(13, 2)); // Output: 10
}
}The C# implementation features binary search with refined boundary checks for the target integer k via CountBelow. A calculated middle value reveals if our target exists below or continues through the search space until convergence.