Split the given string into Odds : Digit DP | Function to check whether a string is an odd number or not ; A function to find the minimum number of segments the given string can be divided such that every segment is a odd number ; Declare a splitdp [ ] array and initialize to - 1 ; Build the DP table in a bottom - up manner ; Initially Check if the entire prefix is odd ; If the Given Prefix can be split into Odds then for the remaining string from i to j Check if Odd . If yes calculate the minimum split till j ; To check if the substring from i to j is a odd number or not ; If it is an odd number , then update the dp array ; Return the minimum number of splits for the entire string ; Driver code
def checkOdd ( number ) : NEW_LINE INDENT n = len ( number ) NEW_LINE num = ord ( number [ n - 1 ] ) - 48 NEW_LINE return ( num & 1 ) NEW_LINE DEDENT def splitIntoOdds ( number ) : NEW_LINE INDENT numLen = len ( number ) NEW_LINE splitDP = [ - 1 for i in range ( numLen + 1 ) ] NEW_LINE for i in range ( 1 , numLen + 1 ) : NEW_LINE INDENT if ( i <= 9 and checkOdd ( number [ 0 : i ] ) > 0 ) : NEW_LINE INDENT splitDP [ i ] = 1 NEW_LINE DEDENT if ( splitDP [ i ] != - 1 ) : NEW_LINE INDENT for j in range ( 1 , 10 ) : NEW_LINE INDENT if ( i + j > numLen ) : NEW_LINE INDENT break ; NEW_LINE DEDENT if ( checkOdd ( number [ i : i + j ] ) ) : NEW_LINE INDENT if ( splitDP [ i + j ] == - 1 ) : NEW_LINE INDENT splitDP [ i + j ] = 1 + splitDP [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT splitDP [ i + j ] = min ( splitDP [ i + j ] , 1 + splitDP [ i ] ) NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT return splitDP [ numLen ] NEW_LINE DEDENT print ( splitIntoOdds ( "123456789123456789123" ) ) NEW_LINE