Given a binary array arr[] and a value array val[]. The task is to find the maximum possible splits of the binary array that can be done such that each segment contains an equal number of 0s and 1s using at most k coins. Each split costs (val[i] – val[j])2, where i and j are the adjacent indices of the split segment.
Examples:
Input: arr[] = {0, 1, 0, 0, 1, 1}, val[] = {2, 5, 1, 3, 6, 10}, k = 20
Output: 1
Explanation: Splits can be done in the following way: 0 1 | 0 0 1 1 and cost = (5 – 1)2 = 16 ≤ 20.Input: arr[] = {1, 0, 0, 1, 0, 1, 1, 0}, val[] = {9, 7, 5, 2, 4, 12, 3, 1], k = 10
Output: 2
Explanation: Splits can be done in the following way: 1 0 | 0 1 | 0 1 1 0
Approach: The task can be solved using dynamic programming (Top-down approach).
Follow the below steps:
- Initialize a 2d matrix say dp of dimensions K * N.
- For every index, there are two choices, whether to make a cut at that index or to not make a cut at that index, provided that the number of zeroes and ones are equal.
- Memoize the values, to be used again
- Maximize the value of count_splits, to get the resultant maximum cuts.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int dp[1001][1001];// Function to find maximum possible splits// in atmost k coins such that each// segment contains equal number of 0 and 1int maximumSplits(int arr[], int val[], int k, int N){ // Base Case if (k < 0) { return INT_MIN; } // If already have a stored value // return it if (dp[k][N] != -1) { return dp[k][N]; } // Count for zeros and ones int zero = 0, one = 0; // Count for number of splits int count_split = 0; int i; // Iterate over the array and // search for zeros and ones for (i = N - 1; i > 0; i--) { arr[i] == 0 ? zero++ : one++; // If count of zeros is equal to // count of ones if (zero == one) { // Store the maximum possible one count_split = max( count_split, 1 + maximumSplits( arr, val, k - pow(val[i] - val[i - 1], 2), i)); } } // If index is at 0, find if // it is zero or one and // increment the count if (i == 0) { arr[0] == 0 ? zero++ : one++; // If count of zero is not equal to // count of one, re-initialize // count_split with 0 if (zero != one) { count_split = 0; } } // Store the returned value in dp[] return dp[k][N] = count_split;}// Driver Codeint main(){ int arr[] = { 1, 0, 0, 1, 0, 1, 1, 0 }; int val[] = { 9, 7, 5, 2, 4, 12, 3, 1 }; int k = 10; int N = sizeof(arr) / sizeof(arr[0]); memset(dp, -1, sizeof(dp)); cout << maximumSplits(arr, val, k, N); return 0;} |
Java
// Java program for the above approachpublic class GFG{static int[][] dp = new int[1001][1001];// Function to find maximum possible splits// in atmost k coins such that each// segment contains equal number of 0 and 1static int maximumSplits(int[] arr, int[] val, int k, int N){ // Base Case if (k < 0) { return Integer.MIN_VALUE; } // If already have a stored value // return it if (dp[k][N] != -1) { return dp[k][N]; } // Count for zeros and ones int zero = 0, one = 0; // Count for number of splits int count_split = 0; int i; // Iterate over the array and // search for zeros and ones for (i = N - 1; i > 0; i--) { if(arr[i] == 0) zero++; else one++; // If count of zeros is equal to // count of ones if (zero == one) { // Store the maximum possible one count_split = Math.max( count_split, 1 + maximumSplits( arr, val, k - (int)Math.pow(val[i] - val[i - 1], 2), i)); } } // If index is at 0, find if // it is zero or one and // increment the count if (i == 0) { if(arr[0] == 0) zero++; else one++; // If count of zero is not equal to // count of one, re-initialize // count_split with 0 if (zero != one) { count_split = 0; } } // Store the returned value in dp[] return dp[k][N] = count_split;} // Driver codepublic static void main(String[] args){ int[] arr = { 1, 0, 0, 1, 0, 1, 1, 0 }; int[] val = { 9, 7, 5, 2, 4, 12, 3, 1 }; int k = 10; int N = arr.length; int i, j; for(i=0;i<1001;i++) { for(j=0;j<1001;j++) { dp[i][j] = -1; } } System.out.println(maximumSplits(arr, val, k, N));}}// This code is contributed by AnkThon |
Python3
# Python Program to implement# the above approachdp = [0] * 1001for i in range(len(dp)): dp[i] = [-1] * 1001# Function to find maximum possible splits# in atmost k coins such that each# segment contains equal number of 0 and 1def maximumSplits(arr, val, k, N): # Base Case if (k < 0): return 10 ** (-9) # If already have a stored value # return it if (dp[k][N] != -1) : return dp[k][N] # Count for zeros and ones zero = 0 one = 0 # Count for number of splits count_split = 0 # Iterate over the array and # search for zeros and ones for i in range(N - 1, 0, -1): if (arr[i] == 0): zero += 1 else: one += 1 # If count of zeros is equal to # count of ones if (zero == one): # Store the maximum possible one count_split = max( count_split, 1 + maximumSplits( arr, val, k - pow(val[i] - val[i - 1], 2), i)) # If index is at 0, find if # it is zero or one and # increment the count if (i == 0): if (arr[i] == 0): zero += 1 else: one -= 1 # If count of zero is not equal to # count of one, re-initialize # count_split with 0 if (zero != one): count_split = 0 # Store the returned value in dp[] dp[k][N] = count_split return dp[k][N]# Driver Codearr = [1, 0, 0, 1, 0, 1, 1, 0]val = [9, 7, 5, 2, 4, 12, 3, 1]k = 10N = len(arr)print(maximumSplits(arr, val, k, N))# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;public class GFG{static int[,] dp = new int[1001, 1001];// Function to find maximum possible splits// in atmost k coins such that each// segment contains equal number of 0 and 1static int maximumSplits(int[] arr, int[] val, int k, int N){ // Base Case if (k < 0) { return Int32.MinValue; } // If already have a stored value // return it if (dp[k, N] != -1) { return dp[k, N]; } // Count for zeros and ones int zero = 0, one = 0; // Count for number of splits int count_split = 0; int i; // Iterate over the array and // search for zeros and ones for (i = N - 1; i > 0; i--) { if(arr[i] == 0) zero++; else one++; // If count of zeros is equal to // count of ones if (zero == one) { // Store the maximum possible one count_split = Math.Max( count_split, 1 + maximumSplits( arr, val, k - (int)Math.Pow(val[i] - val[i - 1], 2), i)); } } // If index is at 0, find if // it is zero or one and // increment the count if (i == 0) { if(arr[0] == 0) zero++; else one++; // If count of zero is not equal to // count of one, re-initialize // count_split with 0 if (zero != one) { count_split = 0; } } // Store the returned value in dp[] return dp[k, N] = count_split;} // Driver codepublic static void Main(String[] args){ int[] arr = { 1, 0, 0, 1, 0, 1, 1, 0 }; int[] val = { 9, 7, 5, 2, 4, 12, 3, 1 }; int k = 10; int N = arr.Length; int i, j; for(i=0;i<1001;i++) { for(j=0;j<1001;j++) { dp[i, j] = -1; } } Console.WriteLine(maximumSplits(arr, val, k, N));}}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript Program to implement // the above approach let dp = new Array(1001); for (let i = 0; i < dp.length; i++) { dp[i] = new Array(1001).fill(-1); } // Function to find maximum possible splits // in atmost k coins such that each // segment contains equal number of 0 and 1 function maximumSplits(arr, val, k, N) { // Base Case if (k < 0) { return Number.MIN_VALUE; } // If already have a stored value // return it if (dp[k][N] != -1) { return dp[k][N]; } // Count for zeros and ones let zero = 0, one = 0; // Count for number of splits let count_split = 0; let i; // Iterate over the array and // search for zeros and ones for (i = N - 1; i > 0; i--) { arr[i] == 0 ? zero++ : one++; // If count of zeros is equal to // count of ones if (zero == one) { // Store the maximum possible one count_split = Math.max( count_split, 1 + maximumSplits( arr, val, k - Math.pow(val[i] - val[i - 1], 2), i)); } } // If index is at 0, find if // it is zero or one and // increment the count if (i == 0) { arr[0] == 0 ? zero++ : one++; // If count of zero is not equal to // count of one, re-initialize // count_split with 0 if (zero != one) { count_split = 0; } } // Store the returned value in dp[] return dp[k][N] = count_split; } // Driver Code let arr = [1, 0, 0, 1, 0, 1, 1, 0]; let val = [9, 7, 5, 2, 4, 12, 3, 1]; let k = 10; let N = arr.length; document.write(maximumSplits(arr, val, k, N)) // This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(N*K)
Auxiliary Space: O(N*K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
