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.
1function findKthNumber(n, k) {
2 function countSteps(n, curr, next) {
3 let steps = 0;
4 while (curr <= n) {
5 steps += Math.min(n + 1, next) - curr;
6 curr *= 10;
7 next *= 10;
8 }
9 return steps;
10 }
11
12 let curr = 1;
13 k--;
14 while (k > 0) {
15 let steps = countSteps(n, curr, curr + 1);
16 if (steps <= k) {
17 curr++;
18 k -= steps;
19 } else {
20 curr *= 10;
21 k--;
22 }
23 }
24 return curr;
25}
26
27// Example usage
28console.log(findKthNumber(13, 2)); // Output: 10The JavaScript solution explores the lexicographical order using a function countSteps, which determines how many numbers exist between current and next nodes in lexicographical order. Adjustments between nodes are made based on whether going deeper or moving forward covers the k-th smallest number.
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 Java solution employs binary search, with countBelow calculating the number of valid integers below a given prefix. The goal is determining the highest prefix whose lexicographical count meets or exceeds k, adjusting our search range accordingly.