Possible cuts of a number such that maximum parts are divisible by 3 | 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
function MaximumNumbers ( s ) { let n = s . length ; let remIndex = [ - 1 , - 1 , - 1 ] ; remIndex [ 0 ] = 0 ; let res = new Array ( n + 1 ) ; for ( let i = 0 ; i < res . length ; i ++ ) { res [ i ] = 0 ; } let r = 0 ; for ( let i = 1 ; i <= n ; i ++ ) { r = ( r + s [ i - 1 ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 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 ] ; } let s = " " ; document . write ( MaximumNumbers ( s ) ) ;