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.
This JavaScript binary search solution evaluates positions by counting numbers lexicographically below the midpoint with countBelow. Each iteration refines the search space in halves, efficiently focusing on the k-th lexicographically numbered target.