440. K-th Smallest in Lexicographical Order LeetCode Solution
In this guide, you will get 440. K-th Smallest in Lexicographical Order LeetCode Solution with the best time and space complexity. The solution to K-th Smallest in Lexicographical Order problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of K-th Smallest in Lexicographical Order
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 <= 109
Complexity Analysis
Time Complexity: O(\log^2 n)
Space Complexity: O(1)
440. K-th Smallest in Lexicographical Order LeetCode Solution in C++
class Solution {
public:
int findKthNumber(int n, int k) {
long ans = 1;
for (int i = 1; i < k;) {
const long gap = getGap(ans, ans + 1, n);
if (i + gap <= k) {
i += gap;
++ans;
} else {
++i;
ans *= 10;
}
}
return ans;
}
private:
long getGap(long a, long b, long n) {
long gap = 0;
while (a <= n) {
gap += min(n + 1, b) - a;
a *= 10;
b *= 10;
}
return gap;
};
}; /* code provided by PROGIEZ */
440. K-th Smallest in Lexicographical Order LeetCode Solution in Java
class Solution {
public int findKthNumber(int n, int k) {
long ans = 1;
for (int i = 1; i < k;) {
final long gap = getGap(ans, ans + 1, n);
if (i + gap <= k) {
i += gap;
++ans;
} else {
++i;
ans *= 10;
}
}
return (int) ans;
}
private long getGap(long a, long b, long n) {
long gap = 0;
while (a <= n) {
gap += Math.min(n + 1, b) - a;
a *= 10;
b *= 10;
}
return gap;
}
} // code provided by PROGIEZ
440. K-th Smallest in Lexicographical Order LeetCode Solution in Python
class Solution:
def findKthNumber(self, n: int, k: int) -> int:
ans = 1
i = 1
while i < k:
gap = self._getGap(ans, ans + 1, n)
if i + gap <= k:
i += gap
ans += 1
else:
i += 1
ans *= 10
return ans
def _getGap(self, a: int, b: int, n: int) -> int:
gap = 0
while a <= n:
gap += min(n + 1, b) - a
a *= 10
b *= 10
return gap # code by PROGIEZ
