Introduction:
We are given a Binary array and a value array. We need to find the maximum possible balanced binary substring splits we can do with at most cost K. Balanced binary substring is a string that contains an equal number of 0s and 1s.
The cost of making a cut is equal to (value[i] - value[j])^2 where i and j are the adjacent indices of the split segment.
Let us see a few examples:-
Input 1:
arr: [0, 1, 0, 0, 1, 1]
value: [1, 2, 3, 4, 5, 6]
K: 1
Output 1:
1
Explanation 1:
Since the value of K is 1, we can only make one cut between the 1st and the 2nd index. The resultant balanced binary substrings would be [0, 1] and [0, 0, 1, 1]. The cost to make this cut is (2 - 3) ^ 2 = 1 and 1<=1.
Input 2:
arr: [0, 1, 0, 1, 0, 0, 1, 1]
value: [1, 3, 5, 6, 9, 10, 12, 14]
K: 14
Output 2:
2
Explanation 2:
We will make the first cut between the 1st and 2nd index which will cost us (3 - 5) ^ 2 = 4 and the second cut between the 3rd and the 4th index which will cost us (6 - 9) ^ 2 = 9. Now, we cannot make any other cuts. The resultant balanced binary substrings would be [0, 1], [0, 1], [0, 0, 1, 1].
Approach 1:
We will write a recursive approach to solve this question. Our recursive function would look like (index, K) where the index will be the index we are currently at and K will store the cost we are left with. At any recursive call, we will run a for loop(let us say for i variable) from the index to the 1st index to count the number of zeros and ones. At any moment if the number of 0s is equal to the number of 1s and the cost to make the cut at the current position is less than K, we will make a recursive call for (i, K - cost) and add 1 to the number of cuts made.
There is one base case. If the number of zeros and ones are not equal and we reach the 0th index, then we can not make any cut. Hence, we need to return 0 in this particular case.
Refer to the below implementation of the above approach.
|
import java.util.*; public class Main { /* This function will return the maximum number of balanced binary substrings we can make in atmost K coins such that each segment contains the equal number of zeroes and ones. */ static int maxSplits(int[] arr, int[] value, int k, int index) { // Base Case if (k < 0) { return Integer.MIN_VALUE; } // Count for zeroes and ones int cnt0 = 0, cnt1 = 0; // Count for number of splits int count_split = 0; int i; /* Iterating the array to find the number of zeroes and ones. */ for (i = index - 1; i > 0; i--) { if(arr[i] == 0) cnt0++; else cnt1++; if (cnt0 == cnt1) { // Store the maximum possible cnt1 count_split = Math.max(count_split, 1 + maxSplits(arr, value, k - (int)Math.pow(value[i] - value[i - 1],2),i)); } } /* if we are at the 0th index we will check if the 0th value is a 0 or 1. */ if (i == 0) { if(arr[0] == 0){ cnt0++; } else{ cnt1++; } /* As discussed in the approach if number of zeros and ones are not equal, we will initialize count_split to 0. */ if (cnt0 != cnt1) { count_split = 0; } } return count_split; } public static void main(String args[]){ Scanner sc = new Scanner(System.in); int n = 8; int arr[] = {0, 1, 0, 1, 0, 0, 1, 1}; int values[] = {1, 3, 5, 6, 9, 10, 12, 14}; int k = 14; System.out.println(maxSplits(arr, values, k, n)); } } |
Output:
2
40+ registered 
