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.
1#include <iostream>
2using namespace std;
3
4long count_steps(long n, long curr, long next) {
5 long steps = 0;
6 while (curr <= n) {
7 steps += min(n + 1, next) - curr;
8 curr *= 10;
9 next *= 10;
10 }
11 return steps;
12}
13
14int findKthNumber(int n, int k) {
15 int curr = 1;
16 k--;
17 while (k) {
18 long steps = count_steps(n, curr, curr + 1);
19 if (steps <= k) {
20 curr++;
21 k -= steps;
22 } else {
23 curr *= 10;
24 k--;
25 }
26 }
27 return curr;
28}
29
30int main() {
31 int n = 13, k = 2;
32 cout << findKthNumber(n, k) << endl; // Output: 10
33 return 0;
34}The C++ code utilizes a function count_steps to calculate the number of steps between consecutive nodes in a lexicographical sense. The main logic is to determine whether the desired k-th number lies within the subtree of the current node or in its sibling, adjusting the root or traversing down as needed.
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.
This C approach implements a binary search to find the k-th smallest lexicographical number. The count_below function determines how many numbers less than a given prefix exist. Depending on this count, we adjust our binary search to quickly converge on the result.