Minimum number of sub | Function that returns true if n is a power of 5 ; Function to return the decimal value of binary equivalent ; Function to return the minimum cuts required ; Allocating memory for dp [ ] array ; From length 1 to n ; If previous character is '0' then ignore to avoid number with leading 0 s . ; Ignore s [ j ] = '0' starting numbers ; Number formed from s [ j ... . i ] ; Check for power of 5 ; Assigning min value to get min cut possible ; ( n + 1 ) to check if all the strings are traversed and no divisible by 5 is obtained like 000000 ; Driver code
def ispower ( n ) : NEW_LINE INDENT if ( n < 125 ) : NEW_LINE INDENT return ( n == 1 or n == 5 or n == 25 ) NEW_LINE DEDENT if ( n % 125 != 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT else : NEW_LINE INDENT return ispower ( n // 125 ) NEW_LINE DEDENT DEDENT def number ( s , i , j ) : NEW_LINE INDENT ans = 0 NEW_LINE for x in range ( i , j ) : NEW_LINE INDENT ans = ans * 2 + ( ord ( s [ x ] ) - ord ( '0' ) ) NEW_LINE DEDENT return ans NEW_LINE DEDENT def minCuts ( s , n ) : NEW_LINE INDENT dp = [ n + 1 for i in range ( n + 1 ) ] NEW_LINE dp [ 0 ] = 0 ; NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( s [ i - 1 ] == '0' ) : NEW_LINE INDENT continue NEW_LINE DEDENT for j in range ( i ) : NEW_LINE INDENT if ( s [ j ] == '0' ) : NEW_LINE INDENT continue NEW_LINE DEDENT num = number ( s , j , i ) NEW_LINE if ( not ispower ( num ) ) : NEW_LINE INDENT continue NEW_LINE DEDENT dp [ i ] = min ( dp [ i ] , dp [ j ] + 1 ) NEW_LINE DEDENT DEDENT if dp [ n ] < n + 1 : NEW_LINE INDENT return dp [ n ] NEW_LINE DEDENT else : NEW_LINE INDENT return - 1 NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = "101101101" NEW_LINE n = len ( s ) NEW_LINE print ( minCuts ( s , n ) ) NEW_LINE DEDENT