### Jon.Snow's blog

By Jon.Snow, 7 months ago,

#### Why iterative?

I learned digit DP few years back but only recently I realised that the recursive solution is sometimes hard to debug and difficult to reason about. So this article aims to provide an iterative solution template that can be extended to solve similar problems.

## Problem Statement

Find count of numbers in range [L, R] such that sum of its digits is a prime number.

• $1 <= L,R <= 10^{18}$

## Basic Idea

• A brute force approach would be to iterate through each number from L to R and check if sum of its digits is prime. This will obviously timeout as constraints are too large.

• So which particular property can we count such that we don't consume too much time/memory?
Sum of digits of numbers! Sum of digits of a number cannot exceed 180 for 18 digits, thus we will have to track only 180 states which will save time and memory.This is the key idea behind most digit DP problems: identify and track a property which is finite and will help us reach the answer.

• We will try to create a function $f(x)$ which returns all good numbers from $[0,x]$. Later we can use $f(R) - f(L-1)$ to find our answer.

## Detailed Explanation

• Let's declare our dp as follows:
    dp[20][2][200]


20 $\rightarrow$ maximum number of digits that our dp will support (18 to be precise)
2 $\rightarrow$ tight condition (explained later)
200 $\rightarrow$ maximum possible sum of digits of a number

For better understanding, try to think of indexes as $dp[i][tight][sum]$

• What does $dp[i][tight][sum]$ even mean?

$dp[i][0][sum] \rightarrow$ count of suffixes that can be formed starting from index i, whose digits add up to $sum$

$dp[i][1][sum] \rightarrow$ count of suffixes that can be formed starting from index i, whose digits add up to $sum$
such that the formed suffix is not greater than corresponding suffix in input string

• Base Cases dp[n][0][0] = dp[n][1][0] = 1
There exists $1$ empty suffix with sum of its digits $=0$

• We will move from right to left while prepending digits at every index till we finally calculate $dp[0][..][..]$ which denotes the entire input string
• What is $tight$?

For every state of dp we also need to know if the current suffix formed includes all unbounded numbers or only the numbers less than or equal to $suffix_{input}$. This information is required because when we are prepending digits to build $dp[i]$ from $dp[i+1]$, we will have to choose between bounded/unbounded suffixes based on our current digit. Try to understand this based on the following recurrence relations.

• We can break $dp[i][tight][sum]$ into subproblems as follows:

$dp[i][0][sum] = \sum\limits_{d=0}^{9} dp[i+1][0][sum-d]$

$dp[i][1][sum] = dp[i+1][1][sum-ss[i]] + \sum\limits_{d=0}^{ss[i]-1} dp[i+1][0][sum-d]$

## Code

int digit_dp(string ss) {
int n = ss.size();

//empty suffixes having sum=0
dp[n][0][0] = 1;
dp[n][1][0] = 1;

for(int i = n-1; i >=0 ; i--) {
for(int tight = 0; tight < 2 ; tight++) {
for(int sum = 0; sum < 200 ; sum++) {
if(tight) {
for(int d = 0; d <= ss[i] - '0' ; d++) {
dp[i][1][sum] += (d == ss[i]-'0') ? dp[i+1][1][sum-d] : dp[i+1][0][sum-d];
}
}
else {
for(int d = 0; d < 10 ; d++) {
dp[i][0][sum] += dp[i+1][0][sum-d];
}
}
}
}
}
int ans = 0;
for(int i = 0; i < 200; i++) {
if(isPrime(i))
ans += dp[0][1][i];
}
return ans;
}


## Complexity

• As obvious from the loops: $O(digits*2*sum*10)$

## End Notes

• Find above SPOJ problem here: GONE
Solution GONE
Solution RAONE
Solution Problem D

• +51

 » 7 months ago, # |   0 Auto comment: topic has been updated by Jon.Snow (previous revision, new revision, compare).
 » 7 months ago, # |   +4 really nice... thanks!!
 » 7 months ago, # | ← Rev. 2 →   +3 Thanks for the tutorial. The template is good.Here is simpler problem one can try : 1036C - Classy NumbersHere is a solution following the above template : 80432206We can get rid of "tight" variable and do it explicitly instead, time complexity does not change : 80431623
•  » » 7 months ago, # ^ |   0 Thanks! I added this problem to End Notes
 » 7 months ago, # |   0 Auto comment: topic has been updated by Jon.Snow (previous revision, new revision, compare).
•  » » 7 months ago, # ^ |   0 Linked solution to last problem.
 » 7 months ago, # |   0 Auto comment: topic has been updated by Jon.Snow (previous revision, new revision, compare).
 » 6 weeks ago, # |   +1 Great Tutorial