Possible cuts of a number such that maximum parts are divisible by 3 | Java program to find the maximum number of numbers divisible by 3 in a large number ; Function to find the maximum number of numbers divisible by 3 in a large number ; store size of the string ; Stores last index of a remainder ; last visited place of remainder zero is at 0. ; To store result from 0 to i ; get the remainder ; Get maximum res [ i ] value ; Driver Code
import java . util . * ; class GFG { static int MaximumNumbers ( String s ) { int n = s . length ( ) ; int [ ] remIndex = { - 1 , - 1 , - 1 } ; remIndex [ 0 ] = 0 ; int [ ] res = new int [ n + 1 ] ; int r = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { r = ( r + s . charAt ( i - 1 ) - '0' ) % 3 ; res [ i ] = res [ i - 1 ] ; if ( remIndex [ r ] != - 1 ) res [ i ] = Math . max ( res [ i ] , res [ remIndex [ r ] ] + 1 ) ; remIndex [ r ] = i + 1 ; } return res [ n ] ; } public static void main ( String [ ] args ) { String s = "12345" ; System . out . println ( MaximumNumbers ( s ) ) ; } }