Digit DP | Data Structures

What is Digit DP?

We've all read and heard about Dynamic Programming and how it makes use of repeating subproblems and memoization to solve a complete larger problem. Digit DP is one such technique that does the same, but in Digit DP, as the name suggests, we play with the digits of a number. This means to reach the final answer, we make use of the digits of a number.

Digit DP is very useful in solving problems that concern a range of numbers, like finding the sum of digits between two numbers $a$ and $b$. Or find how many times a particular digit occurs in the numbers in the range $[a,b]$. These are the situations where digit dp comes in handy. And it is clearly visible by the problem statements that these questions have something to do with the digits of the numbers involved.

Let us find out more about how digit dp works and what is the main idea behind it.

Problem Statement:

Find the total number of times the digit $d$ occurs in the numbers in the range $a$ to $b$, where $a<b$.

For example, let us take the case where a = 5 and b = 10, and d = 1, the answer will be 1 as there is only one digit (10) which has the digit 1.

But how can we solve this using digit dp? We can do so by building a number digit by digit so that it is inside the given range and on the way count the number of times we set a digit as 1. But how can we do this? Let's start with a base case, where in the problem statement, a = 0.

Finding Solution for range $0$ to $b$

To find a solution, we treat our number as a string, basically a string of digits. We need to build numbers digit by digit until they are inside the range given to us in the question. As a = 0, the string is empty in the start, and we can add digits to it.

So, we start adding digits from left to right, so at each point of time, we have a position where we can enter a digit to form a new number, and then recurse for the next position. Now, we need to look at the choices that we have for a particular position. We cannot just add any digit from 0 to 9, because we need to make sure the resulting number satisfies the range.

Let us take an example to understand this better. Let a = 0 and b = 83625. Suppose until now our number string that we are building by adding digits till now is "8362_". In the next recursion, we have to add another digit to the right of 2, but can we add any digit from 0 to 9?

Adding any digit > 5 will result in the number becoming greater than $b$ and thus going out of range. This means that for this particular position we can add only digits from 0 to 5.

On the other hand if the sequence we had built uptil now was "734__", we have no restrictions on any of the places. We can put any digit from 0 to 9 in the remaining places on the right. This is because the first digit '7' itself ensures that the complete number will always be less than $b$ no matter what digits occur to the right of it.

This observation is very important in reaching the digit dp approach. Clearly we have some positions where we need to add digits and build a number inside the given range. The number of positions will depend upon $b$, and will be equal to the number of digits $b$ has.

Now, we have some positions where we need to add digits. We can start from the leftmost position and keep adding digits. At the same time, we will also need some information as to which digits can be added to this position depending upon the previous digits as we saw in the example. How to know this?

One possible way is to keep track of the whole sequence built uptil now, and then check by placing all digits from 0 to 9, and only go ahead with the ones that are less than $b$, and discard the rest. But there is a simpler approach.

We saw using the example, that we have a restriction on the digits we can add only when the sequence built uptil now is the same as the number. If we have added even one number which is less than its corresponding digit of $b$ in the sequence we have made till now, then we have no restrictions.

This follows from the last example, if the sequence built until now is "83___" we cannot put any digit greater than 6 in the next position, but if our sequence was "82___" we have no restrictions, as the digit 2 in the second place ensures that our number will always be smaller than $b$.

This can easily be conveyed using a bool flag variable as a parameter to our recursive function. If this flag variable is set to true, it means we have a restriction and we can add digits from 0 to the digit in $b$ at the corresponding position else the resulting number will go out of range, and if the flag variable is 0, we have no restrictions. Whenever we add a digit to our sequence which is equal to the corresponding digit in $b$, we have to set the flag to 1 and if we are adding a digit smaller than the corresponding digit in $b$, we set the flag to 0 and recurse for the next position.

The initial problem can be solved very easily now because whenever we add the digit $d$ to the sequence we are building, we can add 1 to the answer, and at the end, we will be left with the total number of times the digit $d$ occurs in the range 0 to $a$.

Finding Solution For Given Range

We learned about solving from the range $0$ to some positive integer $b$, but what about the range $a$ to $b$? We already know the solution for $0$ to $b$ and we can also calculate the solution for $0$ to $a-1$ by the same method.

Then, the solution for $a$ to $b$ will simply be

Why is this correct? Because in subtracting solution(0,a-1) from solution(0,b) we make sure all numbers less than $a$ get excluded, thus giving us the soltuion for $a$ to $b$.

States of DP Problem and Solution

So far we have only looked at how we can solve a problem using digit dp, let us now discuss the particulars of the solution.

We know that every DP solution has states, which refers to the total number of parameters required to uniquely define each state in the problem. In this case, we have three states in the DP solution. One state is the position parameter $pos$ which refers to the position where a new digit is to be inserted and it can take the maximum value of the number of digits in $b$.

The second state is the bool $flag$ parameter that we defined earlier which denotes whether we have a restriction on the digits that can be chosen for the current position or not. The third state will be the parameter $cnt$ which denotes the number of digits $d$ we have included till now.

Hence, our memoisation dp table will look like dp[pos][flag][cnt]. Let us look at the complete solution:

Input

Output

In this solution, the dp() function calculates the number of times the digit $d$ occurs in the numbers from 0 to the number represented by the digits array. We calculate this value for $a-1$ and $b$ and subtract them to get the answer for $a$ to $b$.

Time and Space complexity

The time complexity for this solution is $O(10*pos*cnt*flag)$. The maximum value for $pos$ can be 18. This is because we can have integers upto the range of $10^{18}$, so this means that atmost we will have 18 places to fill digits in and hence the value of $pos$ can go upto 18. Similarly, $cnt$ can be 18 and $flag$ can be 0 or 1. So, the time complexity becomes almost constant! The space complexity is $O(pos*cnt*flag)$.

Special Case: Digit d = 0

If you run this solution for digit $d$ = 0, then you will probably get a wrong answer. Let's take a look:

Input

Output

Clearly, the output should have been 1 as 10is the only digit that contains 0 between 1 and 11, but we got 11 extra counts added to the answer. This is because according to our algorithm whenever a 0 is added to the building sequence, we increase the count. But this means that when we are building numbers between 1 to 9 we are adding extra zeroes that are not needed. These numbers are being represented as 01, 02, 03, and so on in the sequence that we built, and the zeroes in the front don't need to be counted as they do not have any significance. If there is a way by which we can know if the number built till now is non-zero or not, then we will know when to count 0 as a digit: count 0 as a digit when the sequence built until now is non-zero and not otherwise.

This can be easily achieved by another bool variable $is_empty$. If this bool variable is true it means that the sequence built so far is empty, and if we are adding a 0 to the sequence we should not count it as a digit as it is at the front of the sequence and if this variable is false, it means our sequence is non-empty and we must count 0 as a digit. The rest of the code implementation remains the same. Let us take a look at the code.

Intput

Output

In this code we have also included a special case when a = 0. In such a case, subtracting 1 from $a$ will lead to a negative value, hence we keep $a$ as it is, and add one to the answer if our digit d = 0.

Including just one bool variable made this implementation very easy. The time complexity for this solution will be $O(10*pos*cnt*isempty*flag)$. The maximum value for $pos$ can be 18.

This is because we can have integers upto the range of $10^{18}$, so this means that atmost we will have 18 places to fill digits in and hence the value of $pos$ can go upto 18. For $cnt$, maximum value can be 18 and $flag$ and $isempty$ can be 0 or 1. So, the time complexity becomes almost constant! The space complexity is $O(pos*cnt*isempty*flag)$.

Example

Let us look at another example. Given two integers $a$ and $b$, find the sum of all digits of the integers that occur between $a$ and $b$. We can use digit dp to find a solution. The only difference from the above mentioned solution will be the variable cnt which will be changed to sum instead and we will add the value of each digit to this variable when we include it.

Input

Output