Cute dynamic programming problem. Here is a Java solution and quick explanation.

The basic question to ask yourself is if I knew subproblem X, I could solve solve problem Y easily.

In this case, problem Y is the number of substrings divisible by 3, the subproblem X is the number of substrings modulo 3 that terminate at the previous character for each possible mod (that is remained 0, 1, and 2).

If you know that at the previous position, there were 2 substrings that terminated there that had a residue of zero, 3 with a residue of one, and 1 with a residue of two, then given the current number and its residue, it is trivial to determine the residues of all the strings that terminate at the current character.

If the current number’s residue is one (e.g., the number is 1, 4, or 7), then the substrings terminating on the previous number with a residue of one now have a residue of two, those with a residue of two now have a residue of zero, and those with a residue of zero now have a residue of one plus 1 more for the current digit since you added a new possible substring of length one.

For example, if you had the string 521438 and you knew the number of strings terminating at the 3 for each residue (2, 2, and 1 respectively for residues 0, 1, and 2), and since 8 mod 3 is 2, you know that all those with residue zero now have residue 2, those with residue two now have residue one, and those with residue one now have residue zero, so (2, 1, and 2 repectively), plus you have a new string of residue 2 so you have 2, 1, and 3 now including the current number.

After you process this in linear time, for all the substrings, you add up the all those with residue zero terminating in all locations.

Here is the code:

// Takes constant space and linear time.
public static void main(String[] args) {

    // You really only need these numbers mod 3.
    int[] s = new int [] { 5,8,1,4,6,2 };
    int left = 3;
    int right = 4;

    int[] found = new int[3];
    int[] last_found = new int[3];
    int sum_found = 0;

    for(int i = left; i <= right; ++i) {

        int res = s[i-1] % 3;

        // leaving the +0 just to show the symmetry.
        // Basically, rotate by the residue and +1 for the new substring.
        // This can be done as a single array, but this is clearer I think.
        // (Also, a proper mathematical modulus would be easier too.)
        found[(res+0) % 3] = last_found[0] + 1;
        found[(res+1) % 3] = last_found[1];
        found[(res+2) % 3] = last_found[2];

        sum_found += found[0];

        // Swap the current and last arrays to make top of the loop simpler.
        int[] swap = last_found;
        last_found = found; 
        found = swap;
    }

    System.out.println( sum_found );
}

Code Edit

The code above removed the table and just keeps track of the last position. It does this with two arrays of length three and swapping between them. It could be done with a single array, but it makes the code more complex (and probably doesn’t even perform better in the micro-optimization sense either).

It is now linear time and constant space while obeying the Left and Right requests. It is like a number of other DP algorithms, if you notice each iteration you are only looking back the the Ith-1 iterations, then you can usually elide the full table.

It also keeps track of the sum along with way (now required since the final array doesn’t exist anymore either). I didn’t fully understand the problem at first, and it appears to have gone through some edits along the way.

Here is a Python solution to the problem. It is basically the same as the solution of @JasonN. It also implements a function that returns the value for different pairs of L and R. It uses less memory when doing the precalculations. You can run it here

#http://programmers.stackexchange.com/q/268022/51441


# s:
#   input digit string that should be checked
# L:
#   the start of the substring that should be investigated
# L:
#   the end of the substring that should be investigated
# cnt:
#   number of 3divisble substrings found so far
# ss0:
#   number of substrings that end at the current position
#   and are divisible by 3
# ss1:
#   number of substrings that end at the current position
#   and have the remainder 1 when divided by 3
# ss2:
#   number of substrings that end at the current position
#   and have the remainder 2 when divided by 3


def ss(s,L,R):
    cnt=0
    (ss0,ss1,ss2)=(0,0,0)
    for i in range(L,R+1):
        r=int(s[i])%3
        if r==0:
            ss0+=1
        elif r==1:
            (ss0,ss1,ss2)=(ss2,ss0,ss1)
            ss1+=1
        elif r==2:
            (ss0,ss1,ss2)=(ss1,ss2,ss0)
            ss2+=1
        cnt+=ss0
    return(cnt)

print(ss('392301',0,len('392301')-1))
print(ss('2035498',2,5))

We know A number is divisble by 3 if the sum of its digits is divisble by 3 (according to the divisibility rules of 3). There is O(n^2) dynamic programming solution (pre-processing) and O(1) constant time for each query.

Let arr[i] is array containing given elements (1....N) and query[i][j] denotes # of substrings divisible by 3 from [i, j]

for(int i = 1; i <= N; i++) {
    query[i][i] = (arr[i] % 3 == 0); // i.e. # of substrings divisible by 3 in [4, 4] is 1 if arr[4] is divisble by 3 otherwise 0
    arr[i] += arr[i - 1]; // arr[i] will contain cumulative sum of 1...i
}

// 
for(int i = N - 1; i > 0; i--) {
    for(int j = i + 1; j <= N; j++) {
        // exclusion-inclusion principle. # of substrings in [1, 7] will be - 
        // #1 sum of # of substrings in [1, 6] and [2, 7]. 
        //    As [2, 6] is included two times, so we need to subtract it one time
        // #2 plus 1 if substring [1, 7] is divisble by 3, 0 otherwise

        // #1
        query[i][j] = query[i][j - 1] + query[i + 1][j] - query[i + 1][j - 1];
        // #2
        // arr[j] contains sum of 1...j. 
        // so arr[j] - arr[i - 1] contains sum of [i...j]
        // number constructed from substring [i...j] is divisble by 3 
        // iff summation of its digits is divible by 3
        query[i][j] += ((arr[j] - arr[i - 1]) % 3 == 0);
    }
}

Note: This will work when the # of elements (Range) is within 3 * 10^3. Otherwise the declation of query[Range][Range] will show compilation error.

If you still don’t get what’s happening on those loopings, use pen and paper to draw a 2D table and fill it up according to above calculation. Then you will surely get a clear intuition 🙂