Given two integers n and k, return the kth lexicographically smallest integer in the…
- User
Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].
Example 1:
Input: n = 13, k = 2 Output: 10 Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10. Example 2:
Input: n = 1, k = 1 Output: 1
Constraints:
1 <= k <= n <= 10^9 class Solution { public: int findKthNumber(int n, int k) { // vector res(n); long long cur = 1; long long count=0; for (int i = 0; i < n; i++) { // res[i] = cur;
if(i==k-1) { break; } if (cur * 10 <= n) { cur *= 10; } else { if (cur >= n) cur /= 10; cur += 1; count+=1; while (cur % 10 == 0) cur /= 10; } } return cur; }};
- Assistant
To solve the problem of finding the
k-th lexicographical number within the range[1, n], it's essential to use an efficient approach that avoids enumerating all numbers up ton, especially sincencan be as large as (10^9).The approach you started with is on the right track but has some inefficiencies and inaccuracies, especially with how the loop iterates up to
ninstead ofk. Instead, we can adopt a more optimized method based on prefix traversal.Optimized Approach: Prefix Traversal
The idea is to traverse the lexicographical tree of numbers (similar to a trie) and count how many numbers are under each prefix. By doing this, you can decide whether to delve deeper into the current prefix or move to the next prefix based on the count.
Steps:
-
Initialize:
- Start with
current = 1(the first number in lex order). - Decrement
kby 1 because we start counting fromcurrent = 1.
- Start with
-
Iterate:
- While
k > 0, calculate the number of numbers (steps) between the current prefix and the next prefix. - If
steps <= k, it means the desired number is not under the current prefix, so move to the next prefix (current += 1) and reducekbysteps. - If
steps > k, it means the desired number is under the current prefix, so go deeper (current *= 10) and decrementkby1(since we're moving down one level in the prefix tree).
- While
-
Calculate Steps:
- To calculate the number of steps between two prefixes (
currentandcurrent + 1), iterate by multiplying the prefix by 10 and accumulating the steps as long as the prefix does not exceedn.
- To calculate the number of steps between two prefixes (
-
Return:
- After the loop,
currentwill be thek-th lexicographical number.
- After the loop,
Implementation:
Here's the optimized C++ implementation based on the above approach:
class Solution { public: int findKthNumber(int n, int k) { long current = 1; k -= 1; // since we start from 1 while (k > 0) { long steps = calculateSteps(current, n); if (steps <= k) { current += 1; k -= steps; } else { current *= 10; k -= 1; } } return current; } private: long calculateSteps(long current, int n) { long steps = 0; long first = current; long last = current; while (first <= n) { steps += std::min(static_cast<long>(n + 1), last + 1) - first; first *= 10; last = last * 10 + 9; } return steps; } };Explanation of the Code:
-
Initialization:
currentstarts at1.kis decremented by1because the first number (1) is already considered.
-
Main Loop (
while (k > 0)):- Calculate Steps: Determines how many numbers exist between the current prefix (
current) and the next prefix (current + 1). - Decide Direction:
- If
stepsis less than or equal tok, the k-th number is outside the current prefix subtree. Move to the next prefix (current += 1) and reducekaccordingly. - If
stepsis greater thank, the k-th number lies within the current prefix subtree. Dive deeper into the subtree (current *= 10) and decrementkby1because we're moving one step down in the prefix tree.
- If
- Calculate Steps: Determines how many numbers exist between the current prefix (
-
Calculating Steps (
calculateStepsfunction):- It calculates the number of valid numbers between the current prefix (
first) and the next prefix (last + 1). - It iteratively multiplies
firstby10and updateslastaccordingly to traverse through all levels of the subtree under the current prefix. stepsaccumulates the count of numbers within the range[first, last], ensuring we don't exceedn.
- It calculates the number of valid numbers between the current prefix (
-
Return Statement:
- Once
kis reduced to0, the current prefix (current) is the k-th lexicographical number.
- Once
Why This Works Efficiently:
- Time Complexity: (O(\log n \times \log n)), which is efficient for (n) up to (10^9).
- Space Complexity: (O(1)), as it uses a constant amount of additional space.
Example Walkthrough:
Let's take your first example where
n = 13andk = 2:-
Initial State:
current = 1k = 1(after decrement)
-
First Iteration:
steps = calculateSteps(1, 13)which returns5(numbers: 1, 10, 11, 12, 13)- Since
5 > 1, dive deeper:current = 10 k = 0(sincek -= 1)
-
Termination:
- The loop ends, and
current = 10is returned, which is correct.
- The loop ends, and
Conclusion
By using the prefix traversal method, the problem is solved efficiently without the need for large loops or extensive memory usage. This approach scales well even for large values of
nandk.Feel free to implement this method and test it against various cases to ensure its correctness and efficiency.
-