Min binary partition

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.

The idea here is to optimize the previous approach using dynamic programming. We are calling some functions, again and again, so we will call them once and store their values in a ‘dp’ array.

The below diagram shows overlapping subproblems and repetitive calculations of functions. The partition functions marked in orange color are repeating again and again.

Algorithm:

• Declare a variable to store the minimum number of partitions, say ‘answer’.
• Declare an array ‘dp’ to avoid repetitive calculations of overlapping subproblems and initialize all its values with -1.
• Call 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 three parameters :

• index: An integer to keep track of the current index of string.
• S: string given in the problem.
• dp: An integer array to store overlapping subproblems.

int partition(index, S, dp) :

• If index >= size of string then return 0 as we have done all partitions of string.
• If ‘dp[index]’ is not equal to -1 then return it as we have already calculated the answer for this subproblem.
• 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 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 ‘isPowerFive’ function returns true then recursively call the ‘partition’ function to make a partition at current index. If 1 + recursive call of ‘partition’ function is less than ‘minimumTillNow’ then update ‘minimumTillNow’ with it.
• Update ‘dp[index]’ with ‘minimumTillNow’.
• 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 zeros.
• Declare variables ‘number’ to keep track of current number, ‘digit’ to get current digit from string, and ‘base’ to keep track of 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.

The idea here is to use iterative dynamic programming here. We will calculate the answer from bottom to top.

Algorithm:

• Declare a variable to store the minimum number of partitions, say ‘answer’.
• Declare an array ‘dp’ to avoid repetitive calculations of overlapping subproblems and initialize all its values with the length of string + 1.
• Run a loop from 1 to the length of the string.
• Run a loop from 0 to i.
• If substring starting from index ‘j’ to the index is the power of five then update ‘dp[ i ]’ as minimum of ‘dp[ i ]’ and ‘dp[ j ]’ + 1. Checking whether the current substring is a power of five is done by the ‘isPowerFive’ function.
• If ‘dp[N]’ equals the length of string + 1 then return -1 as it shows there is no valid partition. Here ‘N’ is the length of the string.
• Return ‘dp[n]’ as we have found the best possible partition.

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 zeros.
• Declare variables ‘number’ to keep track of current number, ‘digit’ to get current digit from string, and ‘base’ to keep track of 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.