Tags: "leetcode", "trie", access_time 2-min read

# K Th Smallest in Lexicographical Order

#### Created: February 13, 2020 by [lek-tin]

##### Last updated: February 13, 2020

Given integers `n` and `k`, find the lexicographically k-th smallest integer in the range from `1` to `n`.

Note: `1 ≤ k ≤ n ≤ 10^9`.

### 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

``````class Solution:
def findKthNumber(self, n: int, k: int) -> int:
if n < k or k < 1:
return 0

if n < 10:
return k

curr = 1
k -= 1
while k > 0:
leap, prev, next = 0, curr, curr+1
while prev <= n:
# update leap
leap += min(n+1, next) - prev
prev *= 10
next *= 10

if leap <= k:
curr += 1
print(leap, "<= k; curr =", curr)
k -= leap
else:
curr *= 10
print(leap, "> k; curr =", curr)
k -= 1

return curr
# Input: n=1300, k=50
# order: [1,10,100,1000,1001,1002,1003,1004,1005,1006,1007,1008,1009,101,1010,1011,1012,1013,1014,1015,1016,1017,1018,1019,102,1020,1021,1022,1023,1024,1025,1026,1027,1028,1029,103,1030,1031,1032,1033,1034,1035,1036,1037,1038,1039,104,1040,1041,1042]
# Output:
# 412 > k; curr = 10
# 111 > k; curr = 100
# 11 <= k; curr = 101
# 11 <= k; curr = 102
# 11 <= k; curr = 103
# 11 <= k; curr = 104
# 11 > k; curr = 1040
# 1 <= k; curr = 1041
# 1 <= k; curr = 1042
``````