Minimum splits in a binary string such that every substring is a power of 4 or 6. | Python 3 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. ; 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
import sys NEW_LINE def isPowerOf ( val , base ) : NEW_LINE INDENT while ( val > 1 ) : NEW_LINE INDENT if ( val % base != 0 ) : NEW_LINE val //= base NEW_LINE DEDENT return True NEW_LINE DEDENT def numberOfPartitions ( binaryNo ) : NEW_LINE INDENT n = len ( binaryNo ) NEW_LINE dp = [ 0 ] * n NEW_LINE if ( ( ord ( binaryNo [ n - 1 ] ) - ord ( '0' ) ) == 0 ) : NEW_LINE INDENT dp [ n - 1 ] = - 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ n - 1 ] = 1 NEW_LINE DEDENT for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT val = 0 NEW_LINE if ( ( ord ( binaryNo [ i ] ) - ord ( '0' ) ) == 0 ) : NEW_LINE INDENT dp [ i ] = - 1 NEW_LINE continue NEW_LINE DEDENT dp [ i ] = sys . maxsize NEW_LINE for j in range ( i , n ) : NEW_LINE INDENT val = ( val * 2 ) + ( ord ( binaryNo [ j ] ) - ord ( '0' ) ) NEW_LINE if ( isPowerOf ( val , 4 ) or isPowerOf ( val , 6 ) ) : NEW_LINE INDENT if ( j == n - 1 ) : NEW_LINE INDENT dp [ i ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( dp [ j + 1 ] != - 1 ) : NEW_LINE INDENT dp [ i ] = min ( dp [ i ] , dp [ j + 1 ] + 1 ) NEW_LINE DEDENT DEDENT DEDENT DEDENT if ( dp [ i ] == sys . maxsize ) : NEW_LINE INDENT dp [ i ] = - 1 NEW_LINE DEDENT DEDENT return dp [ 0 ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT binaryNo = "100110110" NEW_LINE print ( numberOfPartitions ( binaryNo ) ) NEW_LINE DEDENT