Possible cuts of a number such that maximum parts are divisible by 3 | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int MaximumNumbers ( string s ) { int n = s . length ( ) ; vector < int > remIndex ( 3 , -1 ) ; remIndex [ 0 ] = 0 ; vector < int > res ( n + 1 ) ; int r = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { r = ( r + s [ i - 1 ] - '0' ) % 3 ; res [ i ] = res [ i - 1 ] ; if ( remIndex [ r ] != -1 ) res [ i ] = max ( res [ i ] , res [ remIndex [ r ] ] + 1 ) ; remIndex [ r ] = i + 1 ; } return res [ n ] ; } int main ( ) { string s = "12345" ; cout << MaximumNumbers ( s ) ; return 0 ; }