Min binary partition

Easy
0/40
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in companies
WalmartGrabFlipkart limited

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
2
1
101
Sample Output 1 :
1 
1
Explanation of Sample Input 1 :
Test Case 1 :  
Given S = “1”,
1 in base 10 = 1
1 = 5 ^ 0
So, minimum value of K = 1.

Test Case 2 : 
Given S = “101”,
“101” in base 10 = 5
5 = 5 ^ 1
So, minimum value of K = 1.
Sample Input 2 :
2
111
110
Sample Output 2 :
3
-1
Explanation of Sample Input 2 :
Test Case 1 :  
Given S = “111”
We can make three partitions of ‘S’ as “1” + “1” + “1”
1 in base 10 = 1
1 = 5 ^ 0
So minimum value of K = 3.

Test Case 2 : 
Given S = “110”
There is no valid partition of this substring, So we need to print -1.
Hint

Can you check all possible partitions ?

Approaches (3)
Brute force

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.
Time Complexity

O(N ^ N), where ‘N’ is the length of the string.

 

In the worst case we need to check all possible partitions which are O(N ^ N) as for each index in the current recursive stack we are making O(N) recursive calls. Our ‘isPowerFive’ is taking O(N) time as we are running a single loop to calculate it. So overall time complexity will be O(N ^ N) + O(N) = O(N ^ N) 

Space Complexity

O(N), where ‘N’ is the length of the string.

 

Our ‘partition’ function requires O(N) space in the form of recursive stack space. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Min binary partition
Full screen
Console