Here, We see K-th Smallest in Lexicographical Order LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![K-th Smallest in Lexicographical Order LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
K-th Smallest in Lexicographical Order LeetCode Solution
Table of Contents
Problem Statement
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
K-th Smallest in Lexicographical Order Solution C++
class Solution {
public:
int calSteps(int n, long n1, long n2) {
int steps = 0;
while (n1 <= n) {
steps += min((long)n + 1, n2) - n1;
n1 *= 10;
n2 *= 10;
}
return steps;
}
int findKthNumber(int n, int k) {
int curr = 1;
k--;
while (k > 0) {
int steps = calSteps(n, curr, curr + 1);
if (steps <= k) {
curr += 1;
k -= steps;
}
else {
curr *= 10;
k--;
}
}
return curr;
}
};
Code language: HTML, XML (xml)
K-th Smallest in Lexicographical Order Solution Java
class Solution {
public int findKthNumber(int n, int k) {
int prefix=1;
for(int count=1;count<k;){
int currCount=getCountWithPrefix(prefix,prefix+1,n);
if(currCount+count<=k){
count+=currCount;
prefix++;
}else{
prefix*=10;
count++;
}
}
return prefix;
}
private int getCountWithPrefix(long startPrefix,long endPrefix,int max){
int count=0;
while(startPrefix<=max){
count+=Math.min(max+1,endPrefix)-startPrefix;
startPrefix*=10;
endPrefix*=10;
}
return count;
}
}
Code language: PHP (php)
K-th Smallest in Lexicographical Order Solution JavaScript
var findKthNumber = function (n, k) {
function dfs (l, r) {
let nn = BigInt(n);
if (l > nn) {
return 0n;
}
if (r > nn) {
r = nn;
}
return r - l + 1n + dfs(l * 10n, r * 10n + 9n);
}
let kn = BigInt(--k), cu = 1;
while (kn > 0) {
let cs = dfs(BigInt(cu), BigInt(cu));
if (cs <= kn) {
kn -= cs;
cu++;
}
else {
kn -= 1n;
cu *= 10;
}
}
return cu;
};
Code language: JavaScript (javascript)
K-th Smallest in Lexicographical Order Solution Python
class Solution(object):
def findKthNumber(self, n, k):
cur = 1
k -= 1
while k > 0:
steps = self.getSteps(n, cur, cur+1)
if steps <= k:
cur += 1
k -= steps
else:
cur *= 10
k -= 1
return cur
def getSteps(self, n, n1, n2):
steps = 0
while n1 <= n:
steps += min(n+1, n2) - n1
n1 *= 10
n2 *= 10
return steps