Number of sub sequences of a given array that are divisible by n

Question

I have a sequence of numbers say 1,2,4,0 and I have to find number of sequence divisible by 6.

So we will have 0,12,24,120,240 which means answer will be 5,

The problem is that I devised an algorithm which requires O(2^n) time complexity so basically it iterates through all the possibilities which is naive.

Is there some way to decrease the complexity.

Edit1: multiple copy of digit is allowed. for example input can be 1,2,1,4,3 Edit2: digits should be in order such as in above example 42 420 etc are not allowed

code: This code however is not able to take 120 into account

`#include <stdio.h>
 #include<string.h>
 #define m 1000000007
 int main(void) {
 int t;
 scanf("%d",&t);
 while(t--)
 {
    char arr[100000];
    int r=0,count=0,i,j,k;
    scanf("%s",&arr);
    int a[100000];
    for(i=0;i<strlen(arr);i++)
    {
        a[i]=arr[i]-'0';
    }
    for(i=0;i<strlen(arr);i++)
    {
        for(j=i;j<strlen(arr);j++)
        {
            if(a[i]==0)
            {
                count++;
                goto label;
            }
            r=a[i]%6;
            for(k=j+1;k<strlen(arr);k++)
            {
                r=(r*10 + a[k])%6;
                if(r==0)
                count++;
            }
        }
        label:;
        r=0;
    }
    printf("%d\n",count);
 }
 return 0;
}

Answer 1

You can use dynamic programming.

As usual, when we decide to solve a problem using dynamic programming, we start by turning some input values into parameters, and maybe adding some other parameters.

The obvious candidate for a parameter is the length of the sequence. Let our sequence be a[1], a[2], ..., a[N]. So, we search for the value f(n) (for n from 0 to N) which is the number of subsequences of a[1], a[2], ..., a[n] which, when read as numbers, are divisible by D=6. Computing f(n) when we know f(n-1) does not look obvious yet, so we dig into details.

On closer look, the problem we now face is that adding a digit to the end of a number can turn a number divisible by D into a number not divisible by D, and vice versa. Still, we know exactly how the remainder changes when we add a digit to the end of a number.

If we have a sequence p[1], p[2], ..., p[k] and know r, the remainder of the number p[1] p[2] ... p[k] modulo D, and then add p[k+1] to the sequence, the remainder s of the new number p[1] p[2] ... p[k] p[k+1] modulo D is easy to compute: s = (r * 10 + p[k+1]) mod D.

To take that into account, we can make the remainder modulo D our new parameter. So, we now search for f(n,r) (for n from 0 to N and r from 0 to D-1) which is the number of subsequences of a[1], a[2], ..., a[n] which, when read as numbers, have the remainder r modulo D.

Now, knowing f(n,0), f(n,1), ..., f(n,D-1), we want to compute f(n+1,0), f(n+1,1), ..., f(n+1,D-1). For each possible subsequence of a[1], a[2], ..., a[n], when we consider element number n+1, we either add a[n+1] to it, or omit a[n+1] and leave the subsequence unchanged. This is easier to express by forward dynamic programming rather than a formula:

let f (n + 1, *) = 0
for r = 0, 1, ..., D - 1:
    add f (n, r) to f (n + 1, r * 10 + a[n + 1])  //   add a[n + 1]
    add f (n, r) to f (n + 1, r)                  //  omit a[n + 1]

The resulting f (n + 1, s) (which, depending on s, is a sum of one or more terms) is the number of subsequences of a[1], a[2], ..., a[n], a[n+1] which yield the remainder s modulo D.

The whole solution follows:

let f (0, *) = 0
let f (0, 0) = 1  //  there is one empty sequence, and its remainder is 0
for n = 0, 1, ..., N - 1:
    let f (n + 1, *) = 0
    for r = 0, 1, ..., D - 1:
        add f (n, r) to f (n + 1, r * 10 + a[n + 1])  //   add a[n + 1]
        add f (n, r) to f (n + 1, r)                  //  omit a[n + 1]
answer = f (N, 0) - 1

We subtract one from the answer since an empty subsequence is not considered a number.

The time and memory requirements are O (N * D). We can lower the memory to O (D) when we note that, at each given moment, we only need to store f (n, *) and f (n + 1, *), so the storage for f can be 2 * D instead of (N + 1) * D.

An illustration with your example sequence:

-------------------------------
  a[n]           1   2   4   0
 f(n,r)  n   0   1   2   3   4
    r
-------------------------------
    0        1   1   2   3   6
    1        0   1   1   1   1
    2        0   0   1   2   4
    3        0   0   0   0   0
    4        0   0   0   2   5
    5        0   0   0   0   0
-------------------------------

Exercise: how to get rid of numbers with leading zeroes with this solution? Will we need another parameter?