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
< ? php function ispower ( $ n ) { if ( $ n < 125 ) return ( $ n == 1 $ n == 5 $ n == 25 ) ; if ( $ n % 125 != 0 ) return false ; else return ispower ( $ n / 125 ) ; } function number ( $ s , $ i , $ j ) { $ ans = 0 ; for ( $ x = $ i ; $ x < $ j ; $ x ++ ) { $ ans = $ ans * 2 + ( ord ( $ s [ $ x ] ) - ord ( '0' ) ) ; } return $ ans ; } function minCuts ( $ s , $ n ) { $ dp = array_fill ( 0 , $ n + 1 , $ n + 1 ) ; $ dp [ 0 ] = 0 ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { if ( $ s [ $ i - 1 ] == '0' ) continue ; for ( $ j = 0 ; $ j < $ i ; $ j ++ ) { if ( $ s [ $ j ] == '0' ) continue ; $ num = number ( $ s , $ j , $ i ) ; if ( ! ispower ( $ num ) ) continue ; $ dp [ $ i ] = min ( $ dp [ $ i ] , $ dp [ $ j ] + 1 ) ; } } return ( ( $ dp [ $ n ] < $ n + 1 ) ? $ dp [ $ n ] : -1 ) ; } $ s = "101101101" ; $ n = strlen ( $ s ) ; echo minCuts ( $ s , $ n ) ; ? >