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
function ispower ( n ) { if ( n < 125 ) return ( n == 1 n == 5 n == 25 ) ; if ( n % 125 != 0 ) return false ; else return ispower ( parseInt ( n / 125 ) ) ; } function number ( s , i , j ) { var ans = 0 ; for ( var x = i ; x < j ; x ++ ) { ans = ans * 2 + ( s [ x ] - ' ' ) ; } return ans ; } function minCuts ( s , n ) { var dp = Array ( n + 1 ) . fill ( n + 1 ) ; dp [ 0 ] = 0 ; for ( var i = 1 ; i <= n ; i ++ ) { if ( s [ i - 1 ] == ' ' ) continue ; for ( var j = 0 ; j < i ; j ++ ) { if ( s [ j ] == ' ' ) continue ; var num = number ( s , j , i ) ; if ( ! ispower ( num ) ) continue ; dp [ i ] = Math . min ( dp [ i ] , dp [ j ] + 1 ) ; } } return ( ( dp [ n ] < n + 1 ) ? dp [ n ] : - 1 ) ; } var s = " " ; var n = s . length ; document . write ( minCuts ( s , n ) ) ;