Minimum splits in a binary string such that every substring is a power of 4 or 6. | C # 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
using System ; class GFG { static bool isPowerOf ( long val , int b ) { while ( val > 1 ) { if ( val % b != 0 ) val /= b ; } return true ; } static int numberOfPartitions ( string binaryNo ) { int i , j , n = binaryNo . Length ; long val ; int [ ] dp = new int [ 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 . MaxValue ; 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 ] = Math . Min ( dp [ i ] , dp [ j + 1 ] + 1 ) ; } } } if ( dp [ i ] == int . MaxValue ) dp [ i ] = - 1 ; } return dp [ 0 ] ; } public static void Main ( ) { string binaryNo = "100110110" ; Console . Write ( numberOfPartitions ( binaryNo ) ) ; } }