Min binary partition

Posted: 11 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.
Try Problem