Prime Digit Sum

Approach : 

1. Precalculate the prime numbers from 0 to 200 by ‘SeiveOfEratosthenes’.
2. Traverse from each integer from ‘L’ to ‘R’ and for each integer, i find the sum of digits of i.
3. Check if the sum is prime and increase the result accordingly.
    

Algorithm : 
 

• Create and initialize array ‘PRIME[200]’ as true
• Using ‘SeiveOfEratosthenes’ we mark prime numbers in the array ‘PRIME’
• Create a ‘RES’ variable to store the count of good numbers
• Run a For loop from i = ‘L’ to ‘R’
  • Find the sum of digits of i and if the sum is prime increase the result by 1.
• Return ‘RES’

Approach : 

The Sum of digits of a number cannot exceed 9*9 for 9 digits, thus we will have to track only 9*9 states which will save time and memory.
 

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.
 

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

• 20 → maximum number of digits that our DP will support (18 to be precise)
• 2 → tight condition (explained later)
• 200 → 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]→ count of suffixes that can be formed starting from index i, whose digits add up to sum
• DP[i][1][sum]→ 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:

Algorithm : 

      // Function to calculate the number of good numbers between 0 to n.

• countPrime(string S)
  • Create and intialize array ‘prime[200]’ as true
  • Usign ‘SeiveOfEratosthenes’ we mark prime numbers in array ‘prime’
  • Initialize variable ‘N’ = length of ‘S’
  • ‘DP[N][0][0]’ = ‘DP[N][1][0]’ = 1 // Initializing the DP
  • For i = N-1 to ‘0’ // from lsb to msb
    • For tight = 0 to ‘1’
      • For sum = 0 to ‘200’
        • If tight is ‘true’
          • For d = 0 to number at ‘S[i] - 1’
            • Add ‘DP[i+1][0][sum-d]’ to ‘DP[i][1][sum]’
          • Add ‘DP[i+1][1][sum-(S[i] - ‘0’)]’ to ‘DP[i][1][sum]’
        • Else
          • For d = 0 to 9
            • Add ‘DP[i][1][sum]’ to ‘DP[i][1][sum]’
  • Return the sum of all the values at the prime index of ‘DP[0][1]’.

• primeDigitSum(L, R)
  • Return ‘countPrime(string(R))’ - ‘countPrime(string(L-1))’