Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/440.html
440. K-th Smallest in Lexicographical Order
Level
Hard
Description
Given integers n
and k
, find the lexicographically k-th smallest integer in the range from 1
to n
.
Note: 1 ≤ k ≤ n ≤ 109.
Example:
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.
Solution
Starting from 1, let curr
be the current prefix, and the next prefix is curr + 1
. Count the number of integers with prefix curr
. If the number of integers with prefix curr
is greater than k
, then set curr = curr * 10
and use the updated curr
to calculate the next prefix curr + 1
. Otherwise, subtract the number of integers from k
, and set curr = curr + 1
. Repeat the process until k
becomes 0. Finally, return curr
.
-
class Solution { public int findKthNumber(int n, int k) { int curr = 1; k--; while (k > 0) { int steps = getSteps(n, curr, curr + 1); if (steps > k) { curr *= 10; k--; } else { curr++; k -= steps; } } return curr; } public int getSteps(int n, long curr, long next) { int steps = 0; while (curr <= n) { steps += Math.min(n + 1, next) - curr; curr *= 10; next *= 10; } return steps; } }
-
class Solution: def findKthNumber(self, n: int, k: int) -> int: def count(curr): next, cnt = curr + 1, 0 while curr <= n: cnt += min(n - curr + 1, next - curr) next, curr = next * 10, curr * 10 return cnt curr = 1 k -= 1 while k: cnt = count(curr) if k >= cnt: k -= cnt curr += 1 else: k -= 1 curr *= 10 return curr ############ class Solution(object): # naive pre-order traversal on denary tree def _findKthNumber(self, n, k): """ :type n: int :type k: int :rtype: int """ def dfs(cur, n): if self.k == 0: return cur self.k -= 1 if cur == 0: for i in range(1, 10): if i > n: break ret = dfs(i, n) if ret: return ret else: for i in range(0, 10): if cur * 10 + i > n: break ret = dfs(cur * 10 + i, n) if ret: return ret self.k = k return dfs(0, n) # optimized solution def findKthNumber(self, n, k): def getGap(n, ans): gap = 0 start = ans end = start + 1 while start <= n: gap += max(0, min(n + 1, end) - start) start *= 10 end *= 10 return gap ans = 1 k -= 1 while k > 0: gap = getGap(n, ans) if gap <= k: ans += 1 k -= gap else: ans *= 10 k -= 1 return ans
-
class Solution { public: int n; int findKthNumber(int n, int k) { this->n = n; --k; long long curr = 1; while (k) { int cnt = count(curr); if (k >= cnt) { k -= cnt; ++curr; } else { --k; curr *= 10; } } return (int) curr; } int count(long long curr) { long long next = curr + 1; int cnt = 0; while (curr <= n) { cnt += min(n - curr + 1, next - curr); next *= 10; curr *= 10; } return cnt; } };
-
func findKthNumber(n int, k int) int { count := func(curr int) int { next := curr + 1 cnt := 0 for curr <= n { cnt += min(n-curr+1, next-curr) next *= 10 curr *= 10 } return cnt } curr := 1 k-- for k > 0 { cnt := count(curr) if k >= cnt { k -= cnt curr++ } else { k-- curr *= 10 } } return curr } func min(a, b int) int { if a < b { return a } return b }