Maximum possible balanced binary substring splitting, taking at most k

The array in the C programming language has a fixed size, which means that once the size is specified, it cannot be changed; you can neither shrink it or extend it.

As we know, an array is a set of elements of the same data type, which are stored in a contiguous memory area.

Given an array of values ​​v[] and a binary array a[]. The objective is to use as many k coins to divide the binary array as much as is possible while ensuring that each segment has an equal amount of 0s and 1s. i and j are the neighboring indices of the split segment, and the cost of each split is (v[i] - v[j])2.

Problem Statement

Implement a program that finds the largest possible balanced binary substring split, costing at most k.

Example Example 1

Let the Input array be: 
a: [1,0,0, 1, 0, 0, 1, 1]
The given values be: 
v: [7, 8, 9, 10, 11, 12,13,14]
K: 1

Output obtained is: 1

Explanation

Since the value of K is 1, we can make a cut between the first and second index.

In this case, [0, 1] and [0, 0, 1, 1] are the balanced binary substrings of the final result.

Making this cut will cost (8 - 9)^ 2 = 1, and 1 = 1.

Example Example 2

Let the Input array be: 
a: [1,0 1, 0, 1, 1, 0,0]
The given values be: 
v: [2, 4, 7, 10, 11, 12, 13, 14]
K: 14

Output obtained is: 2

Explanation

The first cut will be made between the first and second index that is 4 and 7, costing us (4 - 7)^2 = 9 and the second cut will be made between the third and fourth index that is 7 and 10 , costing us (7 - 10)^ 2 = 9. No more cuts are possible at this time. The balanced binary substrings in this case that would arise are [1, 0], [1, 0], and [1, 1 , 0, 0].

Approach

In order to find maximum possible balanced binary substring splits with at most cost k, we take the following methodology.

Here we take a top-down approach to solve this problem and to find maximum possible balanced binary substring splits with at most cost k.

Use the top-down approach, or more commonly known as the dynamic programming approach. The main advantage of dynamic programming is the improved efficiency of simple recursion. Dynamic programming can be used to optimize any recursive solution that involves repeated calls to the same input. To avoid recomputing the results of subproblems later, the idea is to store them. With this simple optimization, the time complexity is reduced from polynomial to exponential.

Algorithm

The algorithm to find maximum possible balanced binary substring splits with at most cost K is given below.

• Step One - Start

• Step 2 - Define a two-dimensional matrix m

• Step 3 - Define a function to find the largest possible balanced binary substring split.

• Step 4 − Define integer variables zeroCount to count the number of zeros and oneCount to count the number of ones respectively

• Step 5 − Define an integer variable cntSplits to calculate the number of splits

• Step 6 - Iterate over the given array a

• Step 7 − check whether the number of zeros is equal to the number of ones, then store the maximum feasible one

• Step 8 - Assume the index is at position 0, then find out if it is 1 or 0, then increment the count

• Step 9 − set the cntSplits to zero, if count of one and count of zero is unequal.

• Step 10 - Store the resulting values ​​in the matrix

• Step 11 − Print the desired result obtained

• Step 12 − Stop

Example: C program

This is a C program implementation of the above algorithm for finding the largest possible balanced binary substring split, costing at most k.

#include <stdio.h>
#include <limits.h>
#include <string.h>
//Define a two-dimensional matrix m
int m[1001][1001];

//Define a function to find maximum possible //balanced binary substring splits
int maxSplits(int a[], int v[], int k, int s) {
   if (k < 0) {
      return INT_MIN;
   }
   if (m[k][s] != -1) {
      return m[k][s];
   }
   
   //Define integer variables to count the number of zeros and ones 
   // Define an integer variable to count the //number of splits
   int zeroCount = 0, oneCount = 0;
   int cntSplits = 0;
   int i;
   
   //Iterating through the given array a
   for (i = s - 1; i > 0; i--) {
      a[i] == 0 ? zeroCount++ : oneCount++;
      
   // check whether the number of zeros is equal to the number of ones, then store the maximum feasible one
      if (zeroCount == oneCount) {
         cntSplits = cntSplits > (1 + maxSplits(a, v, k - (v[i] - v[i - 1]) * (v[i] - v[i - 1]), i)) ? cntSplits : (1 + maxSplits(a, v, k - (v[i] - v[i - 1]) * (v[i] - v[i - 1]), i));
      }
   }
   
   //Suppose the index is at the position 0, then find whether it is a one or a zero. then increment the count
   if (i == 0) {
      a[0] == 0 ? zeroCount++ : oneCount++;
      
   // set the cntSplits to zero , if count of one and count of zero is unequal.
      if (zeroCount != oneCount) {
         cntSplits = 0;
      }
   }
   
   // store the resultant value in the matrix
   return m[k][s] = cntSplits;
}
int main() {
   int a[] = { 1, 0, 0, 1, 0, 0, 1, 1 };
   int v[] = { 7, 8, 9, 10, 11, 12, 13, 14 };
   int k = 1;
   int s = sizeof(a) / sizeof(a[0]);
   
   //To assign a specific value to a block of memory, we use the memset() function.
   memset(m, -1, sizeof(m));
   printf("%d\n", maxSplits(a, v, k, s));
   return 0;
}

Output

1

in conclusion

Similarly, we can find possible balanced binary substring splits that cost at most K.

In this paper, the challenge of getting a program to find the largest possible balanced binary substring splitting at most cost K is addressed.

C programming code is provided here along with an algorithm to find the largest possible balanced binary substring split, costing at most K.

The above is the detailed content of Maximum possible balanced binary substring splitting, taking at most k. For more information, please follow other related articles on the PHP Chinese website!