### flash_7's blog

By flash_7, history, 5 years ago,

Wrote this article a long ago but during solving a problem recently thought of sharing this article publicly. Hope it will help some contestants to understand the idea clearly.

Digit dp is a very easy technique and also useful to solve many dynamic programming problems. Seeing the name “Digit DP” it’s easy to guess that we are going to do something using the digits. Yes we are actually going to play with digits. Let’s explain the concept using a classical problem.

#### Problem

How many numbers x are there in the range a to b, where the digit d occurs exactly k times in x? There may have several solutions including number theory or combinatorics, but let’s see how we can solve this problem using digit dp.

#### Solve for range (zero to a)

Using digit dp we always focus on building a number satisfying all the conditions. If we finally manage to build that number then we say, yes we have got one ;-) But how we’ll build that number? For the time being let’s say a is zero. So we need to find the total numbers which are not greater than b and also satisfy the given conditions.

#### Building a sequence of digits

Let’s consider the number as a sequence of digits. Let’s name the sequence sq. Initially sq is empty. We’ll try to add new digits from left to right to build the sequence. In each recursive call we’ll place a digit in our current position and will call recursively to add a digit in the next position. But can we place any of the digits from 0 to 9 in our current position? Of course not, because we need to make sure that the number is not getting larger than b.

#### Information we need to place a digit at the current position

Let’s say during the building of the sequence, currently we are at position pos. We have already placed some digits in position from 1 to pos-1. So now we are trying to place a digit at current position pos. If we knew the whole sequence we have build so far till position pos-1 then we could easily find out which digits we can place now. But how?

You can see that, in the sequence sq the left most digit is actually the most significant digit. And the significance get decreased from left to right. So if there exist any position t (1<=t<pos) where sq[t] < b[t] then we can place any digit in our current position. Because the sequence has already become smaller than b no matter which digit we place in the later positions. Note, b[t] means the digit at position t at number b.

But if there was no t that satisfy that condition then at position pos, we can’t place any digit greater than b[pos]. Because then the number will become larger than b.

#### Do we really need the whole sequence?

Now imagine, do we really need that whole sequence to find if a valid t exist? If we placed any digit in our previous position which was smaller than its corresponding digit in b then couldn’t we just pass the information somehow so that we can use it later? Yes, using an extra parameter f1(true/false) in our function we can handle that. Whenever we place a digit at position t which is smaller than b[t] we can make f1 = 1 for the next recursive call. So whenever we are at any position later, we don’t actually need the whole sequence. Using the value of f1 we can know if the sequence have already become smaller than b.

#### Extra condition

So far we focused on building the sequence sq, but we have forgotten that there is an extra condition which is, digit d will have to occur exactly k times in sequence sq. We need another parameter cnt. cnt is basically the number of times we have placed digit d so far in our sequence sq. Whenever we place digit d in our sequence sq we just increment cnt in our next recursive call.

In the base case when we have built the whole sequence we just need to check if cnt is equal to k. If it is then we return 1, otherwise we return 0.

#### Final DP States

If we have understood everything so far then it's easy to see that we need total three states for DP memoization. At which position we are, if the number has already become smaller than b and the frequency of digit d till now.

#### Solve for range (a to b)

Using the above approach we can find the total valid numbers in the range 0 to b. But in the original problem the range was actually a to b. How to handle that? Well, first we can find the result for range 0 to b and then just remove the result for range 0 to a-1. Then what we are left off is actually the result from range a to b.

#### How to solve for range a to b in a single recursion?

In the above approach we used an extra parameter f1 which helped us to make sure the sequence is not getting larger than b. Can’t we do the similar thing so that the sequence does not become smaller than a? Yes of course. For that, we need to maintain an extra parameter f2 which will say if there exist a position t such that sq[t] > a[t]. Depending on the value of f2 we can select the digits in our current position so that the sequence does not become smaller than a. Note: We also have to maintain the condition for f1 parallely so that the sequence remains valid.

Please check this to find the sample code of our initial approach.

#### Problem List

Is there some other problems? Some suggestions are really welcomed :)

• +123

| Write comment?
 » 5 years ago, # | ← Rev. 2 →   +6 I've had this problem for a while, and most probably it's solvable with Digit DP. Maybe it's not, but I haven't found a solution:Given a integer X, find the number of integers i in [l, r] such that i ≤ X and rev(i) ≤ X, where rev(i) is the number formed by reversing the digits of i. For example, rev(1560) = 651 and rev(156) = 651 (not 6510, 65100, etc)Unfortunately I can remember neither the source nor the limits, but probably X < 1018 or something.
 » 5 years ago, # |   0 Check BOI(Baltic) 2013 Numbers, i really liked that one.
 » 5 years ago, # | ← Rev. 2 →   +11 I think you can add this problem. I solved it using Digit DP. I really liked this problem.UPD: Another interesting problem on DIGIT DP https://www.hackerrank.com/contests/morgan-stanley-codeathon-2017/challenges/dreamplay-and-clubbing/problem
•  » » 5 years ago, # ^ |   0 Nice problem. Thank you :)
•  » » 4 years ago, # ^ |   0 Beautiful problem! I used digit dp, bitmask, binary search- all in 1 problem!!
 » 5 years ago, # |   0 Auto comment: topic has been updated by flash_7 (previous revision, new revision, compare).
 » 5 years ago, # |   0 One may find this interesting.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Solved it. A very nice problem. Thanks Vai :)
 » 5 years ago, # |   0 How to solve LIDS ?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 The maximum length of LIDS can be at max 10. So we can check for each length k, in how many ways we can make a number whose LIDS is k. We can then print the result we found for the maximum k.I’m describing the states we need to find the number of ways we can build an LIDS of length k. At which position we are. Has the sequence already become less than y? (0 or 1) Has the sequence already become greater than x? (0 or 1) Did we place at least one non zero digit so far? (To handle the first digit of LIDS) Last digit we have placed in the sequence. Number of total digit in the LIDS sequence. Basically we build two sequence parallelly. One is definitely the whole sequence, another one is the LIDS sequence (Which is the sub sequence of the original sequence). When ever we select a digit we want to place, it becomes the last digit of the original sequence till now. But we can also choose if we want to consider that digit in our LIDS sequence or not.
•  » » » 4 years ago, # ^ |   0 Why do need the fourth state ??@flash_7
•  » » » » 4 years ago, # ^ |   0 To make sure we don't place any leading zeroes. Because if we build a number of length k with some leading zeroes then that number is not really a number of length k.
•  » » » » 11 months ago, # ^ |   0 Yes, I debugged my code and was getting a WA for110000 10000my answer was 1,1 because it did not consider zeros in LIDS.Actual answer is 1,5.
•  » » » 3 years ago, # ^ |   +5 Could you provide more details about how the transitions of this DP are ? Or the accepted code so I could try to understand ?Thanks !
•  » » » » 21 month(s) ago, # ^ |   0 You probably don't need this anymore, but here is a solution: https://ideone.com/QGXuo9
•  » » » 5 months ago, # ^ |   0 but how to count it can you please elaborate?
•  » » » » 4 months ago, # ^ |   0 For those who are struggling, here is my accepted implementation: https://ideone.com/gdavOnFeel free to ask me anything. Glad if i can help.
•  » » 15 months ago, # ^ |   0 Here is the solution to LIDS problem using 3 flags for people who are looking for it. Codeconst int N=11; ll dp[N][N][N][2][2][2]; string a,b; /*counts no. of subsequence of len==need using remaining suffix starting with lastDigit set at (pos-1) + 3 flags*/ ll count(int pos,int lastDigit,int need,int flagA,int flagB,int flagZero) { if(pos==b.size()) return need==0; if(dp[pos][lastDigit+1][need][flagA][flagB][flagZero]!=-1) return dp[pos][lastDigit+1][need][flagA][flagB][flagZero]; int l,r; if(flagA) l=0; else l=a[pos]-'0'; if(flagB) r=9; else r=b[pos]-'0'; ll res=0; for(int i=l;i<=r;i++) { res+=count(pos+1,lastDigit,need,flagA||i>l,flagB||ilastDigit && need && (flagZero || i)) res+=count(pos+1,i,need-1,flagA||i>l,flagB||i>x>>y; a.clear(),b.clear(); while(y) { b.pb(y%10+'0'); y/=10; } while(x || a.length()!=b.length()) { a.pb(x%10+'0'); x/=10; } reverse(all(a)),reverse(all(b)); for(int len=10;len>=1;len--) { memset(dp,-1,sizeof(dp)); if(count(0,-1,len,0,0,0)) { cout<
•  » » » 6 months ago, # ^ |   0 dp[pos][lastDigit+1][need][flagA][flagB][flagZero]=res; why lastDigit+1 ?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Cuz i'm theoretically placing -1 at position (-1) as a dummy digit as it automatically considers all cases. So, 0 points to -1 so offset of 1 is used.
•  » » » » » 6 months ago, # ^ |   0 oh okay thanks
 » 5 years ago, # | ← Rev. 3 →   +6 Some additional problems:- Digit SumRAONELUCIFERNUMTSNGONEChef and special numbers
 » 5 years ago, # |   0 Auto comment: topic has been updated by flash_7 (previous revision, new revision, compare).
 » 5 years ago, # |   0 How to solve "palindromic numbers"?
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 Initially we have the space of all numbers S = {0, 1, 2, 3, ..., 1017}.This space is too big, so we want to reduce it.From all that space we only need to consider the numbers with a special property (being palindrome) P ⊂ S.Now let's consider another space where all of our original numbers are mapped into a different number S2 = {f(0), f(1), f(2), f(3), ..., f(1017)}.There is no point in cosidering this new space S2 instead of original S if it has the same size.Can you think of any mapping f: S⟶S2 that will make the size of S2 manageable?
•  » » » 4 years ago, # ^ |   0 Can't think of solution. Any more suggestions?
 » 5 years ago, # |   +5 Vaiya can you please sort the problems according to difficulty?
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 I didn't solve them all but here goes my order Investigation Sum of Digits Digit Sum Bomb Ra-One Numbers LUCIFER Number G-One Numbers Digit Count Round Numbers Fast Bit Calculations Magic Numbers Maximum Product
•  » » » 4 years ago, # ^ |   0 In the problem "Investigation" whats the logic behind taking the max remainder as 90 only? you have defined the dp states as dp[90][2][90][90]. why 90 ?Target2018
•  » » » » 4 years ago, # ^ |   0 Since the sum of any number less than 2^31 will be less than 83(approx) so any k > 83 wont be able to divide the sum of numbers . So for k > 83 answer should always be 0. That's why we can take max remainder value as 90.
•  » » » » » 4 years ago, # ^ |   0 My sol link :- Solution
•  » » » » » 3 years ago, # ^ |   0 I have the same question The sum of digits of any number less than 2^31 will be less than 90 but the number itself should also be divisible by k So I think the remainder can be greater than 90 and it should be less than 10000 Can you please explain?
•  » » » » » » 3 years ago, # ^ |   +1 Since we are not checking the answer for k > 83 in the question because the answer for k > 83 will always be 0 as I explained above so if while creating a digit we are taking its mod with k (which is always less than 83) the max value of that state won't cross 90.
 » 5 years ago, # |   +5 You can add this problem
 » 5 years ago, # | ← Rev. 2 →   +3 919B - Perfect Number also can be solved by digit DP and it's very amazing if n not greater 10^6
 » 5 years ago, # |   0 how to solve http://codeforces.com/gym/100886/problem/G ? please tell me the state of the dp
•  » » 5 years ago, # ^ |   0
•  » » » 5 years ago, # ^ |   0 thanks !
•  » » » 5 years ago, # ^ |   -10 i have seen the solution , can you please explain the use of FLAG in dp state , how its helping?
 » 5 years ago, # |   0 Which way is more efficient? Double recursion call with 3 states or single recursion call with 4 states?
 » 5 years ago, # |   0 Can Anyone please provide solution for this tutorial also ? I am noob. Sorry for that.
 » 5 years ago, # |   0 I am having really hard time thinking about the time complexity of this approach can anyone please help
 » 4 years ago, # |   +3 what states are used in solving the problem(Cantor)
 » 4 years ago, # |   0 Auto comment: topic has been updated by flash_7 (previous revision, new revision, compare).
 » 4 years ago, # |   +9 Is Classy Numbers also comes in this category?
•  » » 4 years ago, # ^ |   +4 yes
•  » » 4 years ago, # ^ |   +4 It was the simplest problem of DIGIT DP.
•  » » » 4 years ago, # ^ |   0 could you explain the solution
•  » » » » 4 years ago, # ^ |   0 dp states for Classy numbers I used: index,prev_sumhere prev_sum denotes the number of non zero digits. check out my submission : Solution
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +4 Here is my solution using digit DP 42675923, it may help you. There are quite a lot of cases to take care of. The main idea is that for each interval [L, R] the answer is F(R) - F(L - 1). Where F(x) equals the number of classy integers from 0 to x. How to you calculate F(x)? Just using Dynamic Programming.For a number x, the DP looks something like this: dp[i][j][k][0] = number of integers less than x that are i digits long, end in j and they have k digits bigger than 0.dp[i][j][k][1] = number of integers equal to x that are i digits long, end in j and they have k digits bigger than 0.j is going to be between 0..9 and k in the range from 0..3, because a classy number contains no more than 3 non-zero digits.My dynamic has more states than the .Nik.'s but I think it's more intuitive. Hope it's going to help you.
•  » » » » 4 years ago, # ^ |   0 https://www.hackerrank.com/topics/digit-dp this is a good tutorial
•  » » » » 4 years ago, # ^ |   0 Easy to understand solution using the same template as described in the post.Hope it helps :)solution
 » 4 years ago, # |   +1 Another really good question on digit dp: Link
 » 4 years ago, # | ← Rev. 2 →   0 Another good problem in digit dp Balanced Number
 » 4 years ago, # | ← Rev. 3 →   0 Why the for loop start from 0? let a = 100, d = 5, k = 1Please correct me if I'm wrong, because one of the base cases is pos==num.size(), so there will will be state with, 050 chosen right? this is representing number 50? and is that 005 means it's number 5?, because we return 1 when pos == num.size() so we have to fill each digit, this zero a bit difficult to understand.
•  » » 4 years ago, # ^ |   +1 Yes, you are correct. 005 means 5 and 050 means 50. So the way i have written my code, it'll consider all the numbers <= N including the ones whose number of digits is less than the number of digits in N. So it'll work perfectly.But when d = 0, my given code will produce an incorrect output. Because it'll count zero for the numbers who have leading zeroes. For example, for the number 005, it'll count zero two times. Which is wrong. Because we don't consider the leading zeroes in the decimal numbers. You have to handle this case separately.How can we do that? We can use another boolean state, which will keep track if we have placed at least one non zero digits so far. If it's true in any state, then we'll count the zero in that state. Otherwise, we don't. Hope it helps you to understand.
 » 4 years ago, # |   +3 Thanks bro :) .
 » 4 years ago, # |   0 flash_7 can you please tell me how to solve problem 6.Maximum Product by digitDp as i am not able to get what should be the states though i have already solved this question using greedy approach solution but i want to know how it can be solved using digitDp or more precisely is it solvable using digitDp approach or not?
 » 4 years ago, # |   0 In question Investigation I have been using dp states as pos, flag, sum_of_digits, remainder_of_so_far_number.So the dp size should be dp[32][2][10000][10000]but this gives RTE and dp[32][2][101][101] passes.But when k>100 this should give the wrong answer but it is passing My submission https://vjudge.net/solution/18823741 I can't understand why such dp size works?
•  » » 4 years ago, # ^ |   +6 just think about , what could be maximum sum of digits & does the value of k matters if it's greater than the sum of digits ?
•  » » » 4 years ago, # ^ |   0 Sum of digits maximum can be 100 only I know But the remainder_of_so_far_number can be greater than 100 upto value of k i.e.10000
•  » » » » 4 years ago, # ^ |   +6 so , if sod( sum of digits ) is < 100 & k >= 100 , these numbers will never be divisible by k according to this problem , right ? so , if k is >= 100 , we can simply print 0 , otherwise use dp , thus state gets reduced.
•  » » » » » 4 years ago, # ^ |   0 Thanks:) Got it
•  » » » » » » 4 years ago, # ^ |   +6 great :-)
 » 4 years ago, # |   0 What should be the dp state in Palindromic Numbers?
 » 4 years ago, # |   0
 » 4 years ago, # |   0 Thanks a lot, it really helped !! @flash_7
 » 4 years ago, # | ← Rev. 2 →   0 flash_7 How To Solve Palindromic Numbers ??
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # |   +6 Add ENCODING to the list.
 » 3 years ago, # |   +1 Can someone help in the question that was asked in the long challenge of CodeChef in August 2019. Problem Code -ENCODING LINK — https://www.codechef.com/AUG19B/problems/ENCODING
•  » » 3 years ago, # ^ |   0 Hello! There is a very detailed tutorial for this problem on Codechef. If you have further questions, feel free to ask(I was the setter).
 » 3 years ago, # | ← Rev. 2 →   0 A good problem for Digit DP: https://codeforces.com/contest/288/problem/E
 » 3 years ago, # |   0 Thanks for this Article. This following problem is good to be added. Playing with Digits(Hackerearth)
 » 3 years ago, # | ← Rev. 2 →   0 can anyone help me with DIGIT COUNT I am not getting states for my dp array please help
•  » » 3 years ago, # ^ |   0 dp[index][last_digit_placed][flag]
 » 3 years ago, # |   0 thank you so much this is really helpful my digitdp journy has started
 » 3 years ago, # |   0 Really good article about digit DP.
 » 3 years ago, # |   0 E — Almost Everywhere Zero, AtcoderBegCon — 154Similar question to the one discussed in the article. Thank you a lot for the very well explained article!
 » 3 years ago, # |   0 This is also a nice problem as far as I think. Solved now after learning this topic right now. https://codeforces.com/problemset/problem/1036/C
 » 3 years ago, # |   0 I have made a video on digit DP. Digit Dp Link
 » 3 years ago, # |   0 How to solve this problem : calculate the no of times digit d occurs in l to r? sample input : l = 1, r = 22, d = 2 sample output : 6 (2, 12, 20, 21, 22) frequency of 2 is 6. I know a solution having complexty (len(n) * len(n)).
•  » » 3 years ago, # ^ |   0 Can you send the problem link? I want to try my idea.Based on just what you have mentioned, I have a sketch of a solution. HereI'm curious whether this is correct. It could require some tweaks, as for case when d = 0, It also counts the leading zeros.
•  » » » 3 years ago, # ^ |   0 Thanks for your reply.I also did in the same way.
 » 3 years ago, # |   +3 If someone prefers videos, here are few problems and their solutions :Problems (approx 13-14) with solution : https://www.youtube.com/watch?v=Hsnbaixm1A4
 » 2 years ago, # |   +5 Are questions given in the end are sorted according to the increasing level of difficulty ??
 » 2 years ago, # |   0 Thank You for the informative article flash_7
 » 2 years ago, # | ← Rev. 2 →   +1 InvestigationCan somebody tell me the dp state for the above problem? My dp state is dp[pos][rem][f][rem2] = count of numbers when we are at position pos with a remainder rem(sum of digits mod K) and with a remainder rem2(the actual number mod K) The f in my dp state tells us whether the number has already become smaller than the original number or not. Java CodeAlthough the approach is right, my solution got Memory Limit Exceeded. Any ideas for optimizations?
 » 2 years ago, # |   0 Can anyone tell what I'm doing wrong in the question 1-Investigation, code link- https://pastebin.com/sd44xj20
•  » » 2 years ago, # ^ |   0 someguy you initialized 'tight' with 0 instead of 1 in your dp function!
 » 20 months ago, # |   0 Is any editorial available for these problems? If yes please paste the link here. Sorry for Spamming.
 » 19 months ago, # | ← Rev. 3 →   0 flash_7 How to solve maximum product using digit dp .Here is my solution but don't know where it is going wrong
•  » » 7 days ago, # ^ |   0 try 1 1e18
 » 7 months ago, # |   0 you can also add this
 » 6 months ago, # |   0 For the investigation Problem, I wrote this code. Could someone check what is wrong I am doing here : Thanks for the help package A; import java.util.Arrays; import java.util.Scanner; class Solution { public static void main(String... args) { Scanner scn = new Scanner(System.in); int k=1; int tc = scn.nextInt(); while(tc -- > 0) { int a = scn.nextInt(); int b = scn.nextInt(); int c = scn.nextInt(); int ans = solve(a, b, c); System.out.println("Case "+k+": "+ans); k++; } } private static int solve(int a, int b, int k) { long[][][] dp = new long[32][2][9*31]; fill(dp, -1); long X = digitDP(dp, k, String.valueOf(b), 0, 1, 0, 0); fill(dp, -1); long Y = digitDP(dp, k, String.valueOf(a-1), 0, 1, 0, 0); return (int)(X - Y); } private static long digitDP(long[][][]dp, int k, String s, int pos, int tight, int number, int sum) { if(pos == s.length()) { if(number % k == 0 && sum % k == 0 && sum > 0) { // System.out.println(number); return 1; } return 0; } if(dp[pos][tight][sum] != -1) return dp[pos][tight][sum]; long ans = 0; int limit = tight == 1 ? s.charAt(pos) - '0' : 9; for(int digit = 0; digit <= limit; digit ++) { ans += digitDP(dp, k, s, pos + 1, tight == 1 && limit == digit ? 1 : 0, number * 10 + digit, sum + digit); } dp[pos][tight][sum] = ans; return ans; } private static void fill(long[][][]dp, int val) { for(long[][]row : dp) for(long[]d : row) Arrays.fill(d, val); } } 
 » 4 months ago, # |   0 what is dp storing really? I'm having trouble understanding that.
 » 4 months ago, # | ← Rev. 2 →   +3 11.Sum of Digits and 12. Digit Sum are basically the same problem with different input style. I suggest removing Sum of Digits as it's statement is also wrong (asks for range [1,n] but it's actually [a,b]) and it has weird input format. Without changing the ordering, you can substitute CSES Counting Numbers in its place.
 » 7 weeks ago, # |   0 Palindromic numbers. Few things to mention.5 states in dp,dp[pos][len][last_digit][smaller][zerolead].1)pos — where we are? MAXN = 2e1.2)len — current maximum len without leading zeros.Suppose we have some cases like 00121,where len = 3. MAXN = 2e1. 3)last_digit- what kind of digit does store the result? MAXM = 10.4)smaller — has the sequence already become smaller than x? where x is i or j. MAXF = 2.5)zerolead — have we already placed our first digit that is not 0? MAXF = 2.6 states in rec.Let's say rec is ll rec(int pos,int len,int last_digit,ll cur_num,bool smaller,bool zerolead).6)cur_num to continue building our initial number after (pos + 1) > (len + 1) / 2* with just trying to give symmetrical value for O(1),but before that,we could give any value for O(10).ll pw[],where we store power of 10 to get the value from our cur_num for O(1) and put it in order to follow the rules after (len + 1)/2.(P.s.*pos starts from zero).Good luck,have fun.