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 public int findKthNumber(int n, int k) {
3 int curr = 1;
4 k--;
5 while (k > 0) {
6 long steps = countSteps(n, curr, curr + 1);
7 if (steps <= k) {
8 curr++;
9 k -= steps;
10 } else {
11 curr *= 10;
12 k--;
13 }
14 }
15 return curr;
16 }
17
18 private long countSteps(long n, long curr, long next) {
19 long steps = 0;
20 while (curr <= n) {
21 steps += Math.min(n + 1, next) - curr;
22 curr *= 10;
23 next *= 10;
24 }
25 return steps;
26 }
27
28 public static void main(String[] args) {
29 Solution solution = new Solution();
30 System.out.println(solution.findKthNumber(13, 2)); // Output: 10
31 }
32}In the Java implementation, the findKthNumber method determines the k-th smallest number by calculating how many numbers lexicographically lie between nodes using countSteps. If the required number is in the subtree of the current node, we traverse deeper; otherwise, we move to the next sibling.
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.
The Python binary search solution pushes boundaries to find the k-th smallest number based on counts derived from count_below. Each midpoint estimation ensures efficiency by filtering the search space based on valid number counts within lexicographical order limits.