Minimum splits in a binary string such that every substring is a power of 4 or 6. | CPP program for Minimum splits in a string such that substring is a power of 4 or 6. ; Function to find if given number is power of another number or not . ; Divide given number repeatedly by base value . ; return false ; not a power ; Function to find minimum number of partitions of given binary string so that each partition is power of 4 or 6. ; Variable to store integer value of given binary string partition . ; DP table to store results of partitioning done at differentindices . ; If the last digit is 1 , hence 4 ^ 0 = 1 and 6 ^ 0 = 1 ; Fix starting position for partition ; Binary representation with leading zeroes is not allowed . ; Iterate for all different partitions starting from i ; Find integer value of current binary partition . ; Check if the value is a power of 4 or 6 or not apply recurrence relation ; If no partitions are possible , then make dp [ i ] = - 1 to represent this . ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPowerOf ( long val , int base ) { while ( val > 1 ) { if ( val % base != 0 ) val /= base ; } return true ; } int numberOfPartitions ( string binaryNo ) { int i , j , n = binaryNo . length ( ) ; long val ; int dp [ n ] ; dp [ n - 1 ] = ( ( binaryNo [ n - 1 ] - '0' ) == 0 ) ? -1 : 1 ; for ( i = n - 2 ; i >= 0 ; i -- ) { val = 0 ; if ( ( binaryNo [ i ] - '0' ) == 0 ) { dp [ i ] = -1 ; continue ; } dp [ i ] = INT_MAX ; for ( j = i ; j < n ; j ++ ) { val = ( val * 2 ) + ( long ) ( binaryNo [ j ] - '0' ) ; if ( isPowerOf ( val , 4 ) || isPowerOf ( val , 6 ) ) { if ( j == n - 1 ) { dp [ i ] = 1 ; } else { if ( dp [ j + 1 ] != -1 ) dp [ i ] = min ( dp [ i ] , dp [ j + 1 ] + 1 ) ; } } } if ( dp [ i ] == INT_MAX ) dp [ i ] = -1 ; } return dp [ 0 ] ; } int main ( ) { string binaryNo = "100110110" ; cout << numberOfPartitions ( binaryNo ) ; return 0 ; }