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]
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:
5**** and 23*** have different functions f() 5**** and 4**** have different f() functions
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
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():
34**, i = 367**. In this case, we observe that regardless of how we fill in the digits, the resulting number is still ≤ x, so fl = true 78**. In this case, we see that (**) must be ≤ 65, so fl = false78**, sum = 15
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
G(i + 1,new_fl,new_sum) by trying to fill every digit satisfying k into position i
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
f[i][fl][sum]: storing the value G(i,fl,sum)→ At this point, time complexity becomes: O(n x 2 x sum) with a maximum sum of 9*18 = 172.
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 belowG() 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;
}