Number of substrings divisible by 6 in a string of integers | 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. ; Driver Code
def f ( i , m , s , memoize ) : NEW_LINE INDENT if ( i == len ( s ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( memoize [ i ] [ m ] != - 1 ) : NEW_LINE INDENT return memoize [ i ] [ m ] NEW_LINE DEDENT x = ord ( s [ i ] ) - ord ( '0' ) NEW_LINE ans = ( ( ( x + m ) % 3 == 0 and x % 2 == 0 ) + f ( i + 1 , ( m + x ) % 3 , s , memoize ) ) NEW_LINE memoize [ i ] [ m ] = ans NEW_LINE return memoize [ i ] [ m ] NEW_LINE DEDENT def countDivBy6 ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE memoize = [ [ - 1 ] * 3 for i in range ( n + 1 ) ] NEW_LINE ans = 0 NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT if ( s [ i ] == '0' ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT else : NEW_LINE INDENT ans += f ( i , 0 , s , memoize ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s = "4806" NEW_LINE print ( countDivBy6 ( s ) ) NEW_LINE DEDENT