Minimum number of sub | C ++ implementation of the approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  unsigned long long NEW_LINE bool ispower ( ll n ) { if ( n < 125 ) return ( n == 1 n == 5 n == 25 ) ; if ( n % 125 != 0 ) return false ; else return ispower ( n / 125 ) ; } ll number ( string s , int i , int j ) { ll ans = 0 ; for ( int x = i ; x < j ; x ++ ) { ans = ans * 2 + ( s [ x ] - '0' ) ; } return ans ; } int minCuts ( string s , int n ) { int dp [ n + 1 ] ; memset ( dp , n + 1 , sizeof ( dp ) ) ; dp [ 0 ] = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { if ( s [ i - 1 ] == '0' ) continue ; for ( int j = 0 ; j < i ; j ++ ) { if ( s [ j ] == '0' ) continue ; ll 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 ) ; } int main ( ) { string s = "101101101" ; int n = s . length ( ) ; cout << minCuts ( s , n ) ; return 0 ; }