CODEWITHSUNDEEP
c++dynamic-programmingsubsequence
hs2202
hs2202

Reputation: 19

Getting a Non consecutive subsequence divisible by k

I want to find the non consecutive subsequences of a string divisible by a number k (say k = 3). One can call it a modification to the problem https://www.hackerrank.com/contests/w6/challenges/consecutive-subsequences/

For example, Input:

A = {1,2,3,4,1} k = 3

Output:

9

9 because 12,24,21,141,123,231,1231 etc. are possible

What I did for continuous subsequences was

long long get_count(const vector<int> & vec, int k) {
    vector<int> cnt_mod(k, 0);
    cnt_mod[0] = 1;
    int pref_sum = 0;

    for (int elem : vec) {
        pref_sum += elem;
        pref_sum %= k;
        cnt_mod[pref_sum]++;
    }

    long long res = 0;
    for (int mod = 0; mod < k; mod++)
        res += (long long)cnt_mod[mod] * (cnt_mod[mod] - 1) / 2;
    return res;
}

Can you please provide a suitable modification or a new approach(or code) to this to accomplish the required goal?

Thank You :)

Upvotes: 1

Views: 545

Answers (1)

Shubham Sharma
Shubham Sharma

Reputation: 839

Let DP[i][j] : the number of subsequences which form j as modulus when divided by a number . You will need to know some Modular Arithmetic as pre requisite.

The recurrence is simple afterwards :

This is a small piece of code specifically for 3.

DP[0][(str[0]-'0')%3]=1;
for(i=1;str[i];i++)
    {
        DP[i][(str[i]-'0')%3]++;
        for(j=0;j<=2;j++) // A Modulo B is always smaller than B
        {
            DP[i][j] += DP[i-1][j];
            if(DP[i-1][j])
               DP[i][(j*10+str[i]-'0')%3]+=DP[i-1][j];
        }
    }

First is the case when we skip the i th letter , and second case forms a sequence which gives modulo (j*10+str[i]-'0')%3 when i th letter is used. We can drop the if statement

Upvotes: 1

Related Questions