440: K-th-Smallest-in-Lexicographical-Order
Hard

Lowkey this question is hard…

Obviously, a solution that involves computing all the integers in lexicographical order before finding the kth smallest integer will end up TLE-ing.

Now, since having to calculate each individual value in lexicographical order is inefficient (as we do not really care about any value other than the kth smallest integer), it would be stellar if we were able to skip calculating, for example, all the values present between 1 and 2 if we can determine that the kth smallest integer is not between 1 and 2.

In actuality, we can in logarithmic time complexity by computing the number of elements needed to pass to the next consecutive number.

Take for example, n = 110 and k = 64.

Obviously at first glance, it is implied that the 64th smallest integer can not POSSIBLY be between 1 and 2, but how will our algorithm decipher this?! a If we write out the values between 1 and 2 in lexicographical order, we get:

• 1,10,100,101,102,103,104,105,106,107,108,109,11,110,12,13,14,15,16,17,18,19,2

Upon further investigation, realise that you can separate the numbers into certain categories:

• all the values between 1 and 2

  • 1,--,---,---,---,---,---,---,---,---,---,---,--,---,--,--,--,--,--,--,--,--,2
  • there is only 2-1 = 1 value here

• all the values between 10 and 20

  • 1,10,---,---,---,---,---,---,---,---,---,---,11,---,12,13,14,15,16,17,18,19,2
  • there is only 20-10 = 10 values here

• all the values between 100 and 200

  • 1,--,100,101,102,103,104,105,106,107,108,109,--,110,--,--,--,--,--,--,--,--,2
  • there is only 111-100 = 11 values here

• so on and so forth…

After grouping and summing the values together, we calculate that there is 1 + 10 + 11 = 22 numbers needed to pass to go from 1 to 2.

• therefore, we know the 64th smallest integer is not present between 1 and 2 and can now check if it is present between 2 and 3

We can repeat this, until we find out that the 64th smallest integers is present between 5 and 6. Then, since the elements between 5 and 6 are:

• 5,50,51,52,53,54,55,56,57,58,59,6

We can shrink the “borders” by multiplying 5 by a factor of 10 to check if the 64th smallest integers are present between 50 and 51 (and so on and so forth).

This forms the basis of our algorithm.

class Solution {
public:
    int countElementsBetween(long long current, int n) {
        int count = 0;
        long long next = current + 1;
        while (current <= n) {
            count += min((long long) n+1, next)-current;
            current *= 10;
            next *= 10;
        }
        return count;
    }
    int findKthNumber(int n, int k) {
        long long current = 1;
        --k;

        while (k > 0) {
            int currentDifference = countElementsBetween(current, n);
            if (currentDifference <= k) {
                k -= currentDifference;
                ++current;
            } else {
                --k;
                current *= 10;
            }
        }

        return current;
    }
};

code

class Solution {
public:
    int countElementsBetween(long long current, int n) {
        int count = 0;
        long long next = current + 1;
        while (current <= n) {
            count += min((long long) n+1, next)-current;
            current *= 10;
            next *= 10;
        }
        return count;
    }
    int findKthNumber(int n, int k) {
        long long current = 1;
        --k;

        while (k > 0) {
            int currentDifference = countElementsBetween(current, n);
            if (currentDifference <= k) {
                k -= currentDifference;
                ++current;
            } else {
                --k;
                current *= 10;
            }
        }

        return current;
    }
};

complexity