DP Digit

📌 Table of Contents

1. Problem

Given two numbers 0 ≤ L ≤ R ≤ 1e18, count the number of numbers whose sum of digits is a prime number in the range [L…R]

2. Observation

Consider two numbers: 23**** and 14****. We can see that the number of ways to fill in the asterisks (*) so that both numbers satisfy the problem statement is the same. We call this the function f(). If we can calculate f(), we can use that value to solve 32**** or 50****

→ We call f() is the number of ways to fill the asterisks (*) above. If we can calculate f(), we can use that value to solve 32**** or 50****

We can see that f() depends on:

For example, we have L = 0, R = 4356, and two numbers to fill in: A = 43** and B = 34**. We see that the f() functions for these two numbers are different. For example, we could fill in B = 3457, but A = 4357 > R

3. Algorithm

Let G(x) be the number of numbers ≤ x such that the sum of its digits is prime. Then, we have the following three parameters to compute G():

We have the function G(i,fl,sum)

We decompose the number x = d[1…n], where d[i] gives us the i-th digit of x

4. How to calculate G(i, fl, sum)

Example: Consider x = d[4] = 3452, we are filling in the number 34**. Obviously, we see that fl = false. If we fill in 340* or 342*, we see that we can then fill in freely, so new_fl = true. But if we fill in 345*, we again have new_fl = false

Therefore: we have a simple code to calculate new_fl: new_fl = fl & (k == d[i])


lli G(int i, bool fl, int sum){
  if(i > n){
    return <sum is a prime number?>;
  
  lli ans = 0;
  int lim = (tight)? 9 : d[i];
  for(int k = 0; k <= lim; ++k){
    bool nfl = fl & (k == d[i]);
    ans = ans + G(i + 1, nfl, sum + k);
  }
  return ans; 
}
        

Then, we can solve the problem as follows:


<Input>
//convert number R to array d[1..n];
toDigit(R);

//start constructing number at position i = 1, constraint ≤ d[1], and sum = 0
lli x = G(1, 0, 0); 

toDigit(L - 1);
lli y = G(1, 0, 0);
cout << x - y;

//Time complexity: O(R - L) → TLE
        

Why TLE? It's clear that we run the G function for n positions i = [1…n], with each position having a maximum limit of 9. Essentially, this is backtracking to generate all natural numbers from 0…L, 0…R

5. Optimization

→ At this point, time complexity becomes: O(n x 2 x sum) with a maximum sum of 9*18 = 172.

  • This is recursion with memory: when calling the function G(i,fl,sum), if the value f[i][fl][sum] already exists, we return that value immediately, without needing to run the for loop below
  • Why? Because once the entire array f is complete, whenever we call the G() function, we can immediately calculate that value in O(1). Therefore, the time complexity is reduced to the time required to complete the array f: O(n * 2 * sum)
  • 
    lli G(int i, bool fl, int sum){
      if(i > n)
        return <sum la so nguyen to?>;
      
      lli ans = f[i][fl][sum];
      if(ans != -1) return ans;
      ans = 0;
      int lim = (tight)? 9 : d[i];
      for(int k = 0; k <= lim; ++k){
        bool nfl = fl & (k == d[i]);
        ans = ans + G(i + 1, nfl, sum + k);
      }
      return ans; 
    }
            

    6. Problem set