Last updated on October 9th, 2024 at 06:09 pm

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

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

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;
    }
};

2. 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;
    }
}

3. 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;
};

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