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’.

O (((log (max(A,  B))) ^ 2) *  K), where ‘A’, ‘B’ and ‘K’ are the given integers.

We are solving a similar problem twice, so the time complexity depends on the number which has a higher number of digits which is equal to the max of log10(‘A’) and log10(‘B’).

‘idx’ is O(log (max(A,  B))  Sum is also the function of the number of digits O(log (max(A,  B) * 9) and the remainder can range from 0 to ‘K’ -1 so O(‘K’) and ‘isSmall’ can take value 0 or 1. 

So the overall time complexity is O(((log(max(A, B))) * (log(max(A, B)))) * K * 2) = O (((log (max(A,  B))) ^ 2) *  K).

O (log((max (A,  B) ) ^ 2) *  K )   where ‘A’, ‘B’ and ‘K’ are the given integers.

We need O( log( max(A, B) ) ) * 9 space(maximum sum of digits) for ‘isPrime’ array and O( log(max(A, B) ^  2) * K for memoization. Hence space complexity is O(log( max(A,B)) ^2 * K) +O( log(max(A, B)) = O (log( (max(A,  B) )^ 2) *  K ).