Count the subsequences of length 4 divisible by 9

algorithm, division

Solution

If you want to check if a number is divisible by 9, You better look here.

I will describe the method in short:

checkDividedByNine(String pNum) :
If pNum.length < 1
   return false
If pNum.length == 1
   return toInt(pNum) == 9;
Sum = 0
For c in pNum:
    Sum += toInt(pNum)
return checkDividedByNine(toString(Sum))

So you can reduce the running time to less than O(n^3).

EDIT: If you need very fast algorithm, you can use pre-processing in order to save for each possible 4-digit number, if it is divisible by 9. (It will cost you 10000 in memory)

EDIT 2: Better approach: you can use dynamic programming:

For string S in length N:

D[i,j,k] = The number of subsequences of length j in the string S[i..N] that their value modulo 9 == k.

Where 0 <= k <= 8, 1 <= j <= 4, 1 <= i <= N.

D[i,1,k] = simply count the number of elements in S[i..N] that = k(mod 9).
D[N,j,k] = if j==1 and (S[N] modulo 9) == k, return 1. Otherwise, 0.
D[i,j,k] = max{ D[i+1,j,k], D[i+1,j-1, (k-S[i]+9) modulo 9]}.

And you return D[1,4,0].

You get a table in size - N x 9 x 4.

Thus, the overall running time, assuming calculating modulo takes O(1), is O(n).

Problem

To count the subsequences of length 4 of a string of length n which are divisible by 9. For example if the input string is 9999 then cnt=1 My approach is similar to Brute Force and takes O(n^3).Any better approach than this?

Original source