# 440. K-th Smallest in Lexicographical Order

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.
``````

``````class Solution {
public:
int findKthNumber(int n, int k) {
int cur = 1;
--k;
while (k > 0) {
long long step = 0, first = cur, last = cur + 1;
while (first <= n) {
step += min((long long)n + 1, last) - first;
first *= 10;
last *= 10;
}
if (step <= k) {
++cur;
k -= step;
} else {
cur *= 10;
--k;
}
}
return cur;
}
};
``````

Lexicographical Numbers

https://discuss.leetcode.com/topic/64624/concise-easy-to-understand-java-5ms-solution-with-explaination/2

https://discuss.leetcode.com/topic/64462/c-python-0ms-o-log-n-2-time-o-1-space-super-easy-solution-with-detailed-explanations

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation