Number of substrings divisible by 6 in a string of integers - GeeksforGeeks
Given a string consisting of integers 0 to 9. The task is to count the number of substrings which when convert into integer are divisible by 6. Substring does not contain leading zeroes.
Read full article from Number of substrings divisible by 6 in a string of integers - GeeksforGeeks
Given a string consisting of integers 0 to 9. The task is to count the number of substrings which when convert into integer are divisible by 6. Substring does not contain leading zeroes.
As discussed in Check if a large number is divisible by 6 or not. A number is divisible by 6 if last digit is divisible by 2 and sum of digits is divisible by 3.
The idea is to use Dynamic Programming, which enables us to compute answer quickly and efficiently by tracking previously computed answers and using these stored answer instead of recomputing values.
Let f(i, m) be the number of strings starting at index i and sum of their digits modulo 3 (so far) is m and number it represents is even. So, our answer would be
Let x be the ith digit in the string. From f(i, m) we need to find all the even substrings that start in i + 1.
Also, we will get an extra substring if (x + m) itself is divisible by 3 and x is even. So, we get recurrence relation
Let x be the ith digit in the string. From f(i, m) we need to find all the even substrings that start in i + 1.
Also, we will get an extra substring if (x + m) itself is divisible by 3 and x is even. So, we get recurrence relation
// We initially pass m (sum modulo 3 so far) as 0 f(i, m) = ((x + m)%3 == 0 and x%2 == 0) + f(i + 1, (m + x)%3) // Recursive
int
f(
int
i,
int
m,
char
s[],
int
memoize[][3])
{
// End of the string.
if
(i ==
strlen
(s))
return
0;
// If already calculated, return the
// stored value.
if
(memoize[i][m] != -1)
return
memoize[i][m];
// Converting into integer.
int
x = s[i] -
'0'
;
// Increment result by 1, if current digit
// is divisible by 2 and sum of digits is
// divisible by 3.
// And recur for next index with new modulo.
int
ans = ((x+m)%3 == 0 && x%2 == 0) +
f(i+1, (m+x)%3, s, memoize);
return
memoize[i][m] = ans;
}
// Returns substrings divisible by 6.
int
countDivBy6(
char
s[])
{
int
n =
strlen
(s);
// For storing the value of all states.
int
memoize[n+1][3];
memset
(memoize, -1,
sizeof
memoize);
int
ans = 0;
for
(
int
i = 0; i <
strlen
(s); i++)
{
// If string contain 0, increment count by 1.
if
(s[i] ==
'0'
)
ans++;
// Else calculate using recursive function.
// Pass previous sum modulo 3 as 0.
else
ans += f(i, 0, s, memoize);
}
return
ans;
}