Number of substrings divisible by 6 in a string of integers | Java 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
import java . util . * ; class GFG { static int MAX = 100002 ; static int f ( int i , int m , char s [ ] , int memoize [ ] [ ] ) { if ( i == s . length ) { 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 ) ? 1 + f ( i + 1 , ( m + x ) % 3 , s , memoize ) : f ( i + 1 , ( m + x ) % 3 , s , memoize ) ; memoize [ i ] [ m ] = ans ; return memoize [ i ] [ m ] ; } static int countDivBy6 ( char s [ ] ) { int n = s . length ; int [ ] [ ] memoize = new int [ n + 1 ] [ 3 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) { for ( int j = 0 ; j < 3 ; j ++ ) { memoize [ i ] [ j ] = - 1 ; } } int ans = 0 ; for ( int i = 0 ; i < s . length ; i ++ ) { if ( s [ i ] == '0' ) { ans ++ ; } else { ans += f ( i , 0 , s , memoize ) ; } } return ans ; } public static void main ( String [ ] args ) { char s [ ] = "4806" . toCharArray ( ) ; System . out . println ( countDivBy6 ( s ) ) ; } }