Introduction
Suppose you have two integers, 'X' and 'Y,' and you are required to count the number of integers' Z' which satisfy the given constraints, and Z must lie in the range X to Y, both inclusive.
If X and Y are small(1 <= X, Y <= 10^6), you can iterate over all the numbers from X to Y and check which satisfies the given constraints and keeps their count. But if X and Y are large (1 <= X, Y <= 10^18), then this approach is inefficient and gives the verdict "Time Limit Exceeded." So for such cases, we use Digit DP. By the Term "Digit DP," it's clear that we will apply Dynamic Programming on digits.
Also Read About, Byte Array to String
Approach
Let Solve(L, R) give you the solution for the range L to R. For the time being, suppose L is zero. So, to solve for 0 to R, we have to count the total number of non-negative integers Z such that Z satisfies the given constraints and Z is less than or equal to R.
So, if we can find the solution for 0 to X - 1 and 0 to Y, then their difference will give the solution for range X to Y.
Solve(X, Y) = Solve(0, Y) - Solve(0, X - 1)
How to solve for range zero to R??
Let d be the number of digits in the decimal representation of integer R (without leading zeros). Any number less than equal to R can't have the numbers of digits greater than d in its decimal representation. If there is a number less than R having less than d number of digits, we will add leading zeros to it, so we can say that every number less than R has exactly d number of digits in its decimal representation.
Let's consider each number as a sequence of digits. Let's assume that sequence r1,r2,r3,........, rd represents integer R.
Let 'S' be another sequence. S is initially empty.
We will recursively add digits to the next position of S, but we can't add any random digit from 0 to 9 to the sequence. We have to make sure that number is always less than or equal to R.
The index 0 is the most significant digit, and the index d - 1 is the least significant digit. So, if we want to place a digit at index 'i' and index 0 to i - 1 is already filled, then -
- We can put any digit at position 'i' if there exists at least one index 'j' from 0 to 'i' such that S[j] < r[j] because the sequence is already smaller than R, so whatever we add won't create any difference.
- But if no such 'j' exists, we can't put a digit greater than r[i] because the number will become greater than R.
So, we have to pass the next 'index to fill' and the 'current sequence' as a parameter to the recursive call.
This recursive solution is inefficient because we must pass the whole sequence whenever we make the recursive call. But there is no need to pass the entire sequence. We can use a boolean variable 'f' to check whether the current sequence is less than R or not. If f = 1, then the sequence is already smaller than R, and we can add any digit to the next index, but if f = 0, we can't.
So, we can build the sequence, but we have forgotten that the number formed by the sequence must satisfy the given constraints. For that, Let's take an example problem.