4

Given a string of decimal digits, I have to find the number of all substrings divisible by 3 in the range L to R [both inclusive], where L & R are index[1-based] of the specified string
string length <= 100000

I've tried the Naive approach of iterating over all possible substrings & obtaining the answer, but that is not fast enough, especially for multiple pairs L & R.

Then I tried a DP approach. I can obtain all possible substrings divisible by 3 in the whole string, i.e. I'm unable to code the DP solution that gives result for given range.
DP Solution that I tried (not completely sure about It):

for(i=0 ; i<n ; i++) {
    for(j=0 ; j<3 ; j++) {
        dp[i][j]=0 ;
    }
    int curr = (input[i]-'0')%3 ;
    dp[i][curr]++ ;
    if(i) {
        for(j=0 ; j<3 ; j++) {
            if(curr % 3 == 0) { dp[i][j] += dp[i-1][j]; }
            if(curr % 3 == 1) { dp[i][j] += dp[i-1][(j+2)%3]; }
            if(curr % 3 == 2) { dp[i][j] += dp[i-1][(j+1)%3]; }
        }
    }
}
long long sum = 0;
for(i=0 ; i<n ; i++) { sum += dp[i][0] ; }

Can this solution be modified to give results for given range [L,R] ?

After searching alot, I learnt that range queries problems are solved by Segment Tree, but I'm unsure as how Segment Tree + Lazy Propagation can help in this question.

So what is a performant way to count all substrings divisible by 3 in the range L to R [both inclusive]?

EDIT:
Input: First Line contains the given string. Lines after that contain two integers denoting L and R respectively, where both L and R are index(1-based) of string.

Input:
301524 1 2 4 6 3 5

Output:
3 1 1

Explanation:
When L=1 & R=2 we get 3 possible substrings, {3}, {0}, {30} & all these when considered as a decimal number are divisible by 3. Hence the output.
When L=4 & R=6 we get 6 possible substrings, {5} , {52}, {524}, {2}, {24}, {4} & out of these only {24} is divisible by 3.

Repetitions in substrings like 3333 count multiple times, so for L=1 to R=4 the answer would be 10, since we have four times 3, three times 33, two times 333 and one time 3333 (all divisible by 3).

  • 4
    I'm having a hard time understanding your explanation of the problem. Could you give some sample inputs and outputs perhaps? For example, if the string was "31012" would the substrings be "3" and "12" and the correct answer 15? – Ixrec Jan 4 '15 at 20:31
  • Of note, your {} are mismatched. Where does the ll part belong? I assume that ll is a long long, but that isn't defined in the example. – user40980 Jan 4 '15 at 20:32
  • I've made the edits. – Aalok Jan 4 '15 at 20:54
  • It may possibly be helpful in finding efficient algorithms to solve this to realise that if a number is divisible by 3 then so is the sum of all the digits in its decimal representation. – Jules Jan 4 '15 at 21:38
  • 2
    Good exercise ... took me 4 hours to code a (seemingly) correct solution with dynamic programming with O(N). Seems not quite a "beginner level" question. – rwong Jan 5 '15 at 0:13
6

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.

  • I think you saw the question of previous edits. Someone made the wrong edits. Sorry for that. I did this DP solution to get count of all substrings divisible by 3 in whole string but the question is to find the count of substrings in given range [L,R]. Is it possible to make changes to this DP solution so that we can get count in given range? Please check the question again because I've made the edits in It. – Aalok Jan 5 '15 at 6:38
  • So you want to process once and query multiple times? Can't you take this solution then process forward once and backwards once. Now you know how many substrings are divisive by 3 that start at a position too. Make the cumulative sum of each array and do the math? I'll do it tomorrow if nobody does. Alternatively you add another dimension and an inner loop to keep track of starting positions too. – JasonN Jan 5 '15 at 6:59
  • +1 you can avoid storing in an 3*n-array tab if you do the summation of all already in the for loop. Then you only need a three element array tab – miracle173 Jan 5 '15 at 8:35
  • @brown so for calculating the 1-10^5 we need to add all the data.Is anybody having any idea how segment tree help here on decreasing the query time (as in case of segment tree this answer can be given in O(1))? – RATHI Jan 5 '15 at 20:34
  • @RATHI you can preprocess it in quadratic time and get constant time lookups with just a simple table approach I'm pretty sure. At worst, the lookup would be linear w.r.t the size of the substring. – JasonN Jan 5 '15 at 21:21
1

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))
  • Same as mine now. I didn't understand only one query was needed, but after removing the full table, they come down to the same thing (in both space and time, I just make the arrays explicit). The Python multiple assignment definitely makes it simple. I like that. – JasonN Jan 5 '15 at 18:49
  • ss_cnt[R] - ss_cnt[L-1] isn't going to return the number of substrings divisible by 3 within that range. Subtracting ss_cnt[L-1] doesn't remove the substrings that start before L and end between L and R (inclusive). – Rushil Paul Jan 8 '15 at 22:55
  • For example for the string '2035498', ss(2,5) will return 9 whereas the actual answer is 6 – Rushil Paul Jan 8 '15 at 22:56
  • @Rushil you are right, I will try to repair this as soon as possible. – miracle173 Jan 9 '15 at 0:57
  • @Rushil the error is removed now but the running time is now O(n) for each function call – miracle173 Jan 9 '15 at 7:02
0

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

  • Can you explain what is happening inside j loop? Little more explanation regarding how query[i][j] is obtained.. – Aalok Jan 11 '15 at 9:32
  • @Aalok check the edits – Kaidul Islam Jan 11 '15 at 10:59

protected by gnat Jan 5 '15 at 20:39

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.