Min binary partition
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.
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.
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.
You do not need to print anything, it has already been taken care of. Just implement the given function.
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.
- 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.