Magical Numbers

Let, magicalNumbers(x, y) = magical number between x and y(inclusive)

Then, magicalNumbers(A, B) = magicalNumbers(1, B) - magicalNumbers(1, A -1).

Let's solve the above two sub-problem magicalNumbers(1, X) individually, 

The idea is to use digit - dp.

• We will form a sequence of numbers that is less than equal to ‘X’.
• Use an extra variable ‘isSmall’ to keep track of whether the number formed till now is smaller than ‘X’ or not.
• If the sequence of numbers has become small then we can put the next digit till 9.
• Otherwise, the limit of the next digit will be till digit in number ‘X’ at that position.
• Keep the track of sum and remainder after attaching the new digit.
• The number of digits in ‘A‘ and ‘B’ can maximum go till 11. So the sum of digits can maximum go till 11 * 9 = 99. So we will precalculate whether ‘sum’ is prime or not using a sieve.
• The maximum remainder can go till K - 1.
• To avoid repetition of subproblems we can use memoization.

Algorithm :

Consider the global array isPrime [130 ], if ‘i’ is prime then isPrime[ i ] = 1 else 0 and 4D array for memoization ‘dp[13][130][1005][3]’.

• Let ‘A’, ’B’, and ‘K’ be the given numbers.
• Initialize the ‘isPrime’ array with the ‘1’ call function ‘sieve’.
• Declare ‘countNumber(X, K)’ function to get the magic number from 1 to ‘X.’
• Call function countNumbers(B, K) and store the return value in ‘ans1’.
• Call function countNumbers(A-1, K) and store the return value in ‘ans2.
• Return ans1 - ans2.

Description of countNumbers(num, K) function:

• Take an array ‘vec’, to store all the digits of num.
• Run loop while num is not equal to zero
  • Push back (‘num’ % 10) in ‘vec’
• Reverse the ‘vec’ array
• Initialize ‘dp’ with -1.
• Call helper(vec, 0, 0, 0, K, 0) function and store the return value in ‘ans’.
• Return ‘ans’.

Description of helper(vec, idx, sum, rem, K, isSmall):

The ‘helper’ function returns the number of magical numbers which are less than or equal to the sequence of numbers in the ‘vec’ array. It takes four-parameter (‘vec’, current index, the sum of digits till current index, the remainder of a sequence of the number formed till current index, ‘K’,  ‘isSmall’ variable if it is 1, means current sequence of numbers are smaller than the given sequence in ‘vec’ else equal.  

• If ‘vec’ size is equal to ‘idx’
  • If isPrime[sum] is equal to 1 and rem is equal to 0.
    • Return 1
  • Else
    • return 0
• If dp[idx][sum][rem][isSmall] is not equal to -1
  • Return dp[idx][sum][rem][isSmall]
• Take a variable ‘limit’, that store the limit of current index
  • If isSmall is 1
    • ‘limit’ is equal to 9.
  • Else
    • ‘limit’ is equal to vec[idx]
• Take a variable ‘ans’ initialize it to zero.
• Run a loop from 0 to equal to ‘limit’
  • If isSmall is 0 and counter ‘i’ is equal to limit
    • Do recursive call on helper(vec, idx +1, sum + i, (rem * 10 + ‘i’ ) % ‘K’, ‘ K’, ‘isSmall’) function and add the return value to ‘ans’
  • Else
    • Do recursive call on helper(vec, idx +1, sum + i, (rem * 10 + ‘i’ ) % ‘K’, ‘ K’, 0) function and add the return value to ‘ans’
• Update dp[idx][sum][rem][isSmall] = ‘ans’
• Return ‘ans’.