Count the subsequences of length 4 divisible by 9

Question

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?

Answer 1

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

Answer 2

Assuming that the subsequence has to consist of consecutive digits, you can scan from left to right, keeping track of what order the last 4 digits read are in. That way, you can do a linear scan and just apply divisibility rules.

If the digits are not necessarily consecutive, then you can do some finangling with lookup tables. The idea is that you can create a 3D array named table such that table[i][j][k] is the number of sums of i digits up to index j such that the sum leaves a remainder of k when divided by 9. The table itself has size 45n (i goes from 0 to 4, j goes from 0 to n-1, and k goes from 0 to 8).

For the recursion, each table[i][j][k] entry relies on table[i-1][j-1][x] and table[i][j-1][x] for all x from 0 to 8. Since each entry update takes constant time (at least relative to n), that should get you an O(n) runtime.

Answer 3

How about this one:

/*NOTE: The following holds true, if the subsequences consist of digits in contagious locations */ 

public int countOccurrences (String s) {
    int count=0;
    int len = s.length();
    String subs = null;
    int sum;

    if (len < 4)
        return 0;
    else {
        for (int i=0 ; i<len-3 ; i++) {
            subs = s.substring(i, i+4);
            sum = 0;

            for (int j=0; j<=3; j++) {
                sum += Integer.parseInt(String.valueOf(subs.charAt(j)));
            }

            if (sum%9 == 0)
                count++;
        }           
        return count;
    }   
}