Jon.Snow's blog

By Jon.Snow, 7 months ago, In English

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
 
 
 
 
  • Vote: I like it
  • +51
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Jon.Snow (previous revision, new revision, compare).

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

really nice... thanks!!

»
7 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Thanks for the tutorial. The template is good.

Here is simpler problem one can try : 1036C - Classy Numbers

Here is a solution following the above template : 80432206

We can get rid of "tight" variable and do it explicitly instead, time complexity does not change : 80431623

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Jon.Snow (previous revision, new revision, compare).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Jon.Snow (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Great Tutorial