# Min binary partition

Posted: 11 Mar, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### You are given a string ‘S’ of size ‘N’ where ’S’ contains only characters ‘0’ and ‘1’. Your task is to divide ‘S’ into ‘K’ contiguous substrings such that the following conditions hold true :

``````1. Let ‘X’ be a binary number formed by reading a substring of ‘S’ from left to right.
2. ‘X’ must not contain leading zeroes.
3. The decimal equivalent of ‘X’ must be a power of 5.
4. K must be the minimum possible.
``````
##### Note :
``````If no such ‘K’ possible, then you need to return -1.
``````
##### Input Format :
``````The first line of input contains an integer 'T' representing the number of test cases.

The first and the only line of each test case contains a single string, ‘S’.
``````
##### Output Format :
``````For each test case, print the minimum possible value of K. If no such ‘K’ possible, then you need to print -1.

The output of each test case will be printed in a separate line.
``````
##### Constraints :
``````1 <= T <= 5
1 <= N <= 100
‘S’ contains only characters ‘0’ and ‘1’.
Where ‘T’ is the number of test cases, ‘N’ is the length of the given string.
``````
##### Note :
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
Approach 1

The idea here is to check all possible partitions. For each index ‘i’ if substring from index ‘i’ to some index ‘j’ is a power of 5 then we will have two options either make a partition from the index or not. So, we will try both of these options and choose the one that gives us the minimum result.

Algorithm:

• Declare a variable to store the minimum number of partitions, say ‘answer’.
• Run the ‘partition’ function to get the minimum number of partitions and store it in ‘answer’.
• If ‘answer’ = size of string + 1 then return -1 else return ‘answer’. As the value of ‘answer’ as the size of string + 1 shows, no valid partition exists.

Description of ‘partition’ function

This function will take two parameters :

• index: An integer to keep track of the current index of string.
• S: a string given in the problem.

int partition(index, S) :

• If index >= size of string then return 0 as we have done all partitions of string.
• Declare a variable to keep track of the minimum partition of the string starting from the current index, say ‘minimumTillNow’.
• Declare an empty string to keep track of the current string, say ‘cur’.
• Run a loop from index to size of the string
• Add current character to string ‘cur’.
• Check if ‘cur’ is a power of five by calling the function ‘isPowerFive’.
• If the ‘isPowerFive’ function returns true then recursively call ‘partition’ function to make a partition at the current index. If 1 + recursive call of ‘partition’ function is less than ‘minimumTillNow’ then update ‘minimumTillNow’ with it.
• Return ‘minimumTillNow’.

Description of ‘isPowerFive’ function

This function will take one parameter :

• S: binary string which we need to check.

bool isPowerFive( S ) :

• If the first character of ‘S’ is ‘0’ then return false as the string cannot have leading zeroes.
• Declare variables ‘number’ to keep track of the current number, ‘digit’ to get a current digit from the string, and ‘base’ to keep track of the current base of the number.
• Run a loop from the length of the string to 0.
• Calculate the current digit using the current character.
• Add digit * base to ‘number'.
• Multiply ‘base’ by 2.
• Run a loop till the number is divisible by 5.
• Divide ‘number’ by 5.
• If ‘number’ equals 1 then return true else, return false.