Leetcode 440 Solution

This article provides solution to leetcode question 440 (k-th-smallest-in-lexicographical-order)
Categories:
Tags:
Access this page by simply typing in "lcs 440" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/k-th-smallest-in-lexicographical-order

Solution

class Solution {
public:
    int findKthNumber(int n, int k) {
        int64_t curr = 1;
        int i = 0;

        while (k != 1)
        {
            int64_t start = curr;
            int64_t end = curr;
            int64_t cnt = 1;

            while (start * 10 <= (int64_t)n)
            {
                start *= 10;
                end = min((int64_t)n, end * 10 + 9);
                cnt += end - start + 1;
            }

            if (cnt >= k)
            {
                curr *= 10;
                k--;
            }
            else
            {
                curr++;
                k -= cnt;
            }
        }

        return curr;
    }
};