Number of substrings divisible by 6 in a string of integers | C ++ program to calculate number of substring divisible by 6. ; Return the number of substring divisible by 6 and starting at index i in s [ ] and previous sum of digits modulo 3 is m . ; End of the string . ; If already calculated , return the stored value . ; Converting into integer . ; 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 . ; Returns substrings divisible by 6. ; For storing the value of all states . ; If string contain 0 , increment count by 1. ; Else calculate using recursive function . Pass previous sum modulo 3 as 0. ; Driven Program
#include <bits/stdc++.h> NEW_LINE #define MAX  100002 NEW_LINE using namespace std ; int f ( int i , int m , char s [ ] , int memoize [ ] [ 3 ] ) { if ( i == strlen ( s ) ) return 0 ; if ( memoize [ i ] [ m ] != -1 ) return memoize [ i ] [ m ] ; int x = s [ i ] - '0' ; int ans = ( ( x + m ) % 3 == 0 && x % 2 == 0 ) + f ( i + 1 , ( m + x ) % 3 , s , memoize ) ; return memoize [ i ] [ m ] = ans ; } int countDivBy6 ( char s [ ] ) { int n = strlen ( s ) ; int memoize [ n + 1 ] [ 3 ] ; memset ( memoize , -1 , sizeof memoize ) ; int ans = 0 ; for ( int i = 0 ; i < strlen ( s ) ; i ++ ) { if ( s [ i ] == '0' ) ans ++ ; else ans += f ( i , 0 , s , memoize ) ; } return ans ; } int main ( ) { char s [ ] = "4806" ; cout << countDivBy6 ( s ) << endl ; return 0 ; }