Efficient Algorithm to count number of subsequences divisible by 6

Question

Given a string of decimal digits, I have to find the number of all subsequences divisible by 6.

1 ≤ value of String ≤ 10^6

I've tried the naive approach of iterating over all possible subsequences and obtaining the answer, but that is not fast enough, especially with such a huge upper bound on the string length. Then I tried a DP approach but was unable to code DP solution for given range. Can someone please provide any lead in this Problem?

Sample Input
1232
Output
3
Strings Possible - 12,12,132
//Ans should be modulo 10^9 + 7

Below is the DP code(not completely sure about it) for finding the total number of subsequences divisible by 3.Now to check for 6, we also need to incorporate the divisibility by 2 which is creating problem for me.

for(i=0 ; i<n ; i++) {
    for(j=0 ; j<3 ; j++) {
        dp[i][j]=0 ;
    }
    int dig = (str[i]-'0')%3 ;
    dp[i][dig]++ ;
    if(i>0) {
        for(j=0 ; j<3 ; j++) {
            if(dig % 3 == 0) { 
               dp[i][j] += dp[i-1][j];
             }
            if(dig % 3 == 1) {
               dp[i][j] += dp[i-1][(j+2)%3];
             }
            if(dig % 3 == 2) {
               dp[i][j] += dp[i-1][(j+1)%3];
             }
        }
    }
}
long long ans = 0;
for(i=0 ; i<n ; i++) { 
    ans += dp[i][0] ;
}
return ans;

Answer 1

Let SS(x, k, m) = the number of subsequences of the string x representing a number that's equal to k modulo m.

SS([], k, m) = 1 if k == 0 otherwise 0   -- (see footnote at end)
SS(x + [d], k, m) = SS(x, k, m) + sum(SS(x, j, m) where j*10+d == k modulo m)

That is, if you add a digit to x, then the subsequences that sum to k are subsequences of x that sum to k, plus subsequences of x that sum to j where (10*j) plus the new digit is k modulo m.

That turns into a nice dynamic program, which if N is the length of the string and m the number you want subsequences to be divisible by, runs in O(Nm + m^2) time and uses O(m) space. For m=6, this is O(N) time and O(1) space.

# count subsequences with a sum divisible by m.
def subseq(N, m):
    a = [1] + [0] * (m - 1)
    indexes = [[j for j in xrange(m) if (10*j-i)%m == 0] for i in xrange(m)]
    for digit in N:
        a = [a[i] + sum(a[j] for j in indexes[(i - digit) % m]) for i in xrange(m)]
    return a[0] - 1

print subseq(map(int, '1232'), 6)

footnote: the definition of SS counts the empty list as 0 but the empty string isn't a valid number, so the function subtracts one before returning.

Answer 2

This problem can be solved in linear time , O(N), and linear space O(N),N being length of string if we are two consider only substrings. I am trying to build an algorithm for subsequences.

Key points:

1. All the substrings that are divisible by 6 are divisible by 2 and 3 and we will focus on divisibility by these two numbers.

2. This means all candidate substrings must end with either 0 or 2 or 4 or 6 or 8, to satisfy divisibility by 2 AND

3. Sum of digits of the substring must be divisible by 3.

Now first we take an array arr, of length N. We fill is such that

arr[i] = 1 , if ith digit in substring is 0 or 2 or 4 or 6 or 8.

else  arr[i] = 0.

This can be easily done in single traversal of the string.

What we achieve is now we know that all are candidate substrings will end at index i of string such that arr[i] = 1, because we have to satisfy divisibility by 2.

Now take another array arr1,initialized to 0 for all indexes.We fill it such that

arr1[i] = 1, only if sum of digits from index 0 to index i is divisible by 3 

or from index j to i is divisible by 3, such that j < i.

else arr1[i] = 0

For filling up of array arr1, algorithm is as follows:

sum = 0
for(i = 0 to length of string - 1)
{
 sum = sum + digit at index i;
 if(sum%3 == 0)
 {
  arr1[i] = 1 
  sum = 0
 }
}

Now we must take care of the fact even if sum of digits from 0 to index i is divisible by 3, it is possible that sum of digits is also divisible by 3 from index j to i , such that 0 < j < i.

For this we need another array, that keeps track of how many such substrings we have found till yet.

Let the array be track, such that

track[i] = x, if there are x number of 1's in array arr1 for indices j < i.

We don't need another traversal we can modify our previous algorithm as:

initialize array track to be 0 for all entries.
sum = 0
found = -1
for(i = 0 to length of string - 1)
{
 sum = sum + digit at index i;
 if(sum%3 == 0)
  {
    arr1[i] = 1 
    ++found
    track[i] = found 
    sum = 0
}

Now comes the important part which is counting,

Claim:

A substring ending at index i will only contribute to count iff:

arr[i] == 1 and arr1[i] == 1

It is clear because we have to satisfy divisibility by both 2 and 3. And the contribution towards count would be:

count = count + track[i] + 1

1 is added because of j < i in

track[i] = x, if there are x number of 1's in array arr1 for indices j < i.

The algorithm is fairly easy to implement, take that up as an exercise.

Answer 3

Exponential (for general case) recursive solution which translates to linear if the max value that match can represent is 1e6.

def recurse(x, substr, input):
   if x%6 == 0:
     print(x)
   if len(substr) == 6: // as the value represented by string may not be > 1e6
     return
   if input:
     recurse(x+input[0], substr + input[0], input[1:]) // grow the "window"
     recurse(x, substr, input[1:]) // shift the "window"

input = "123163736395067251284059573634848487474"

recurse(input)