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 <stdio.h>
2
3long count_steps(long n, long curr, long next) {
4 long steps = 0;
5 while (curr <= n) {
6 steps += (next > n + 1) ? n + 1 - curr : next - curr;
7 curr *= 10;
8 next *= 10;
9 }
10 return steps;
11}
12
13int findKthNumber(int n, int k) {
14 int curr = 1;
15 k--;
16 while (k > 0) {
17 long steps = count_steps(n, curr, curr + 1);
18 if (steps <= k) {
19 curr++;
20 k -= steps;
21 } else {
22 curr *= 10;
23 k--;
24 }
25 }
26 return curr;
27}
28
29int main() {
30 int n = 13, k = 2;
31 printf("%d\n", findKthNumber(n, k)); // Output: 10
32 return 0;
33}The given C implementation finds the k-th smallest number in a lexicographical manner using a tree traversal strategy. The helper function count_steps calculates how many numbers lie between the current root and its next sibling. This counting allows us to decide if we should move down to the next level (using the current root as a prefix) or move to the next sibling node.
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.
1using namespace std;
long count_below(long n, long prefix) {
long count = 0, factor = 1;
while (prefix <= n) {
count += min(factor, n - prefix + 1);
prefix *= 10;
factor *= 10;
}
return count;
}
int findKthNumber(int n, int k) {
int low = 1, high = n;
while (low < high) {
int mid = low + (high - low) / 2;
long count = count_below(n, mid);
if (count < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
int main() {
int n = 13, k = 2;
cout << findKthNumber(n, k) << endl; // Output: 10
return 0;
}With a binary search in C++, findKthNumber narrows down the range of possible k-th smallest numbers by checking the count of numbers less than the current midpoint. Using count_below, the program efficiently determines if we should search higher or lower in the space.