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.
1using System;
2
3class Solution {
4 public int FindKthNumber(int n, int k) {
5 int curr = 1;
6 k--;
7 while (k > 0) {
8 long steps = CountSteps(n, curr, curr + 1);
9 if (steps <= k) {
10 curr++;
11 k -= (int)steps;
12 } else {
13 curr *= 10;
14 k--;
15 }
16 }
17 return curr;
18 }
19
20 private long CountSteps(long n, long curr, long next) {
21 long steps = 0;
22 while (curr <= n) {
23 steps += Math.Min(n + 1, next) - curr;
24 curr *= 10;
25 next *= 10;
26 }
27 return steps;
28 }
29
30 public static void Main() {
31 Solution sol = new Solution();
32 Console.WriteLine(sol.FindKthNumber(13, 2)); // Output: 10
33 }
34}In this C# solution, the FindKthNumber method iterates to find the k-th element lexicographically by working the tree structure created by numbers' prefixes. Like other implementations, it uses CountSteps helper to decide whether to go down into a subtree or forward.
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.