given string of decimal digits, have find number of subsequences divisible 6.
1 ≤ value of string ≤ 10^6 i've tried naive approach of iterating on possible subsequences , obtaining answer, not fast enough, such huge upper bound on string length. tried dp approach unable code dp solution given range. can please provide lead in problem?
sample input 1232 output 3 strings possible - 12,12,132 //ans should modulo 10^9 + 7 below dp code(not sure it) finding total number of subsequences divisible 3.now check 6, need incorporate divisibility 2 creating problem 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;
this problem can solved in linear time , o(n), , linear space o(n),n being length of string if 2 consider substrings. trying build algorithm subsequences.
key points:
1. substrings divisible 6 divisible 2 , 3 , focus on divisibility these 2 numbers.
2. means candidate substrings must end either 0 or 2 or 4 or 6 or 8, satisfy divisibility 2 and
3. sum of digits of substring must divisible 3.
now first take array arr, of length n. fill such that
arr[i] = 1 , if ith digit in substring 0 or 2 or 4 or 6 or 8. else arr[i] = 0. this can done in single traversal of string.
what achieve know candidate substrings end @ index of string such arr[i] = 1, because have satisfy divisibility 2.
now take array arr1,initialized 0 indexes.we fill such that
arr1[i] = 1, if sum of digits index 0 index divisible 3 or index j divisible 3, such j < i. else arr1[i] = 0 for filling of array arr1, algorithm follows:
sum = 0 for(i = 0 length of string - 1) { sum = sum + digit @ index i; if(sum%3 == 0) { arr1[i] = 1 sum = 0 } } now must take care of fact if sum of digits 0 index i divisible 3, possible sum of digits divisible 3 index j i , such 0 < j < i.
for need array, keeps track of how many such substrings have found till yet.
let array track, such that
track[i] = x, if there x number of 1's in array arr1 indices j < i. we don't need traversal can modify our previous algorithm as:
initialize array track 0 entries. sum = 0 found = -1 for(i = 0 length of string - 1) { sum = sum + digit @ index i; if(sum%3 == 0) { arr1[i] = 1 ++found track[i] = found sum = 0 } now comes important part counting,
claim:
a substring ending @ index contribute count iff:
arr[i] == 1 , arr1[i] == 1 it clear because have satisfy divisibility both 2 , 3. , contribution towards count be:
count = count + track[i] + 1 1 added because of j < i in
track[i] = x, if there x number of 1's in array arr1 indices j < i. the algorithm easy implement, take exercise.
