Count the number of number x that has digit sum equal the digit sum of x*m

Question

I was trying to solve the following problem but I am stuck. I think it is an dynamic programming problem. Could you please give some ideas?

Problem:

Given a positive number n (n<=18) and a positive number m (m<=100). Call S(x) is sum of digits of x. For example S(123)=6 Count the number of integer number x that has n digits and S(x)=S(x*m)

Example:

n= 1, m= 2 result= 2

n= 18, m=1 result = 1000000000000000000

Thanks in advance.

Answer 1

First, we need to come up with a recursive formula:

Starting from the least significant digit (LSD) to the most significant digit (MSD), we have a valid solution if after we compute the MSD, we have S(x) = S(x*m)

To verify whether a number is a valid solution, we need to know three things:

• What is the current sum of digit S(x)
• What is the current sum of digit S(x*m)
• What is the current digit.

So, to answer for the first and last, it is easy, we just need to maintain two parameters sumand digit. To compute the second, we need to maintain two additional parameters, sumOfProduct and lastRemaining.

• sumOfProduct is the current S(x*m)
• lastRemaining is the result of (m * current digit value + lastRemaining) / 10

For example, we have x = 123 and m = 23

• First digit = 3

  sum = 3
  digit  = 0
  sumOfProduct += (lastRemaining + 3*m) % 10 = 9
  lastRemaining = (m*3 + 0)/10 = 6
  

• Second digit = 2

  sum = 5
  digit = 1
  sumOfProduct += (lastRemaining + 2*m) % 10 = 11
  lastRemaining = (m*2 + lastRemaining)/10 = 5
  

• Last digit = 1

  sum = 6
  digit = 2
  sumOfProduct += (lastRemaining + m) % 10 = 19
  lastRemaining = (m + lastRemaining)/10 = 2
  

  As this is the last digit, sumOfProduct += S(lastRemaining) = 21.

So, x = 123 and m = 23 is not a valid number. Check x*m = 2829 -> S(x*m) = S(2829) = 21.

So, we can have a recursive formula with state (digit, sum, sumOfProdut, lastRemaining).

Thus, our dynamic programming state is dp[18][18*9 + 1][18*9 + 1][200] (as m <= 100, so lastRemaining not larger than 200).

Now the dpstate is over 300 MB, but if we use an iterative approach, it will become smaller, using about 30MB