LC 2999: Intuitive | Binary Search | Lexicographically Nth Number.

Find the problem description here. If you would like to read the solution in leetcode platform, find it here.

Intuition

So, basically, I tried to compute the combinations in which the suffix appears. If you think about it, if the finish is a 5-digit number and the given suffix is a 2-digit number then, you have three positions to fill up.

_ _ _ suffix

and if limit = 4 then, for each position, you have 5 choices (include '0' as well)

0 0 0 suffix
0 0 1 suffix
0 0 2 suffix
0 0 3 suffix
0 0 4 suffix
0 1 0 suffix and so on...

We have a bunch of numbers whose count is equal to $(limit + 1)^{positions}$ , and we need to select the few which satisfy our condition of lying between the given start and the finish.

How? Find out the first number that is greater than or equal to the start and the last number that is lesser than or equal to the finish. As simple as it gets!

But, do we need to calculate each and every number? NO!!

We can actually calculate the $n^{th}$ number using n alone. In the above example, how many numbers start with 0? Answer is 25. '0' followed by '0 - 4' combinations. Same goes with '1', '2', and others. So, we have (limit + 1) slots each having (total / (limit + 1)) numbers. And there after, each slot here have sub-slot whose count is 5 numbers each and so on. We can just calcualte the $n^{th}$ number like this.

Now, we have a RANGE, it is SORTED, and we can get some number at some index, what can we do? BINARY SEARCH!!

My solution is quite intuitive if you think about it. I didn't get the intuition for the digit DP though because I didn't solve a single question with digit DP before.

Approach

Calculate the number of positions we need to fill before finish.
Calculate the number of combinations we totally have.
Now, to build the $n^{th}$ number, I followed the same method I described above. I get the each slot count and devise it down further.
Now, two simple binary searches is all it takes. A binary search to find the first number index that is greater than or equal to the given start.
A binary search to find the last number index that is lesser than or equal to the given finish.
Our answer is the number of numbers that are between these indices which is given $(finishIndex - startIndex + 1)$ .

Complexity

Time complexity: For binary search: $O(log(n))$ where $n = (limit + 1)^{positions}$ . For constructing the $n{th}$ combination: $O(positions)$ . Total: $O(p * log(n))$ where p = number of positions to fill and $n = (limit + 1)^{positions}$ .
Space complexity: $O(1)$

Code

typedef long long ll;

class Solution {
public:
    long long getLexicographicallyNthNumber(int limit, ll n, ll total, ll pos) {
        ll number = 0;
        int tens = 10;
        n--;
        // we need to fill all the positions
        while (pos) {
            ll slotN = total / limit;
            ll slot = n / slotN;
            // add it to the number
            number = number * tens + slot;
            
            n %= slotN;
            total = slotN;
            pos--;          // one position is done
        }

        return number;
    }

    long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
        int pos = to_string(finish).length() - s.length();  // number of positions to fill
        long long suffix = stoll(s);
        if (pos <= 0) {
            return suffix >= start && suffix <= finish;
        }
        // computing the total possibilities
        ll total = pow(limit + 1, pos);

        long long tens = pow(10, s.length());

        // find the first number that is greater than or equal to start
        ll left = 1, right = total;
        while (left < right) {
            ll mid = left + (right - left) / 2; // lower mid
            ll number = getLexicographicallyNthNumber(limit + 1, mid, total, pos);
            number = number * tens + suffix;
            if (number < start) {
                left = mid + 1; // exclude mid
            } else {
                right = mid;    // mid can be an answer
            }
        }
        ll startIndex = left;
        
        // find the last number that is lesser than or equal to finish
        left = 1, right = total;
        while (left < right) {
            ll mid = left + (right - left + 1) / 2; // upper mid
            ll number = getLexicographicallyNthNumber(limit + 1, mid, total, pos);
            number = number * tens + suffix;
            if (number > finish) {
                right = mid - 1;    // exclude mid
            } else {
                left = mid;         // mid can be an answer
            }
        }
        ll endIndex = left;

        return endIndex - startIndex + 1;
    }
};

good luck!