Header Ad

Leetcode K-th Smallest in Lexicographical Order problem solution

In this Leetcode K-th Smallest in Lexicographical Order problem solution we have given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].

Leetcode K-th Smallest in Lexicographical Order problem solution


Problem solution in Python.

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        x = [*map(str, range(1, n+1))]
        x.sort()
        return x[k-1]



Problem solution in Java.

class Solution {
    
    private int countSteps(long left, long right, int n) {
        int res = 0;
        while(left <= n || right <= n) {
            res += Math.min(n+1, right) - left;
            left *= 10;
            right *= 10;
        }
        return res;
    }
    public int findKthNumber(int n, int k) {
        if(k == 0) return 0;
        int curr = 1;
        k--;
        while(k > 0) {
            int steps = countSteps(curr, curr+1, n);
            if(steps <= k) {
                curr++;
                k -= steps;
            } else {
                curr *= 10;
                k--;
            }
        }
        return curr;
    }
}


Problem solution in C++.

class Solution {
public:
    using ll = long long;
    int findKthNumber(int n, int k) {
        ll temp = n, ret = 0;
        int nums = 0, retLen = 1, len = 0;
        while(temp > 0) len++, temp /= 10;
        while(nums != k) {
            if(nums > k) ret = (ret-1)*10, retLen++;
            else if(ret%10 == 9) ret *= 10, retLen++;
            else ret++;
            nums = 0, temp = ret;
            for(int i = retLen; i < len; i++) temp *= 10;
            for(int i = 1; i <= len; i++) {
                int div = pow(10, len-i);
                int start = pow(10, i-1);
                ll dived = (temp>n&&i==len)?n:temp;
                int cur = dived/div;
                nums += cur - start + 1;
                double lg = log10(dived/ret);
                if(retLen < i && dived > ret && lg > 0 && lg == (int)lg) nums--;
            }
        }
        return ret;
    }
};


Post a Comment

0 Comments