Maximum partitions possible of given Array with cost at most K and equal count of odd and even elements
Given two integers N, K, and an array, arr[] of size N, containing an equal number of even and odd elements, and also given that the cost of partitioning the array by making a cut between index i and i+1 is equal to the abs(arr[i]-arr[i+1]), the task is to find the maximum partitions of the array, such that each partition has an equal number of odd and even elements and has a total cost less than or equal to K.
Examples:
Input: N = 6, K = 4, arr[] = {1, 2, 5, 10, 15, 20}
Output: 1
Explanation:
The only possible way to partition is by making a cut between index 1 and index 2.
Cost of partition = |arr[1]( =2)- arr[2](= 5)| = 3, which is less than and equal to K
Arrays after partition: {1, 2} and {5, 10, 15, 20}.Input: N = 4, K = 10, arr[] = {1, 3, 2, 4}
Output: 0
Approach: The given problem can be solved based on observations that it is always possible to make a valid partition by making a cut between the index i and i+i, if the count of even and odd elements in the prefix of i is equal. Follow the steps to solve the problem.
- Initialize a vector V to store the costs of all possible cuts in the array.
- Also, initialize variables, say odd as 0 and even as 0 which store the count of even and odd elements.
- Traverse the array arr[], using the variable i and perform the following steps:
- If the current element is odd, then increment odd by 1. Otherwise, increment even by 1.
- If the value of odd is equal to the value of even, then append the value of |arr[i]–arr[i+1]| to V.
- Sort the vector V in ascending order.
- Initialize an integer variable ans as 1, to store the number of partitions of the array.
- Traverse the vector V, using the variable i and perform the following steps:
- If the value of V[i] is less than or equal to K then update the value K as K – V[i] and increment ans by 1.
- Otherwise, break out of the loop.
- Finally, after completing the above steps, print the value of ans as the answer obtained.
Below is the implementation of the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum // partitions of the array with // equal even and odd elements // with cost less than k int maximumcut( int arr[], int N, int K) { // Stores count of odd elements int odd = 0; // Stores count of even elements int even = 0; // Stores the cost of partitions vector< int > V; for ( int i = 0; i < N - 1; i++) { // Odd element if (arr[i] % 2 == 1) { odd++; } // Even element else { even++; } // Partition is possible if (odd == even) { int cost = abs (arr[i] - arr[i + 1]); // Append the cost of partition V.push_back(cost); } } // Stores the maximum number of // partitions int ans = 0; // Sort the costs in ascending order sort(V.begin(), V.end()); // Traverse the vector V for ( int i = 0; i < V.size(); i++) { // Check if cost is less than K if (V[i] <= K) { // Update the value of K K = K - V[i]; // Update the value of ans ans++; } else { break ; } } // Return ans return ans; } // Driver code int main() { // Given Input int arr[] = {1, 2, 5, 10, 15, 20}; int N = sizeof (arr) / sizeof (arr[0]); int K = 4; // Function call cout << maximumcut(arr, N, K); return 0; } |
Java
// Java code for the above approach import java.util.ArrayList; import java.util.Arrays; class GFG { // Function to find the maximum // partitions of the array with // equal even and odd elements // with cost less than k public static int maximumcut( int arr[], int N, int K) { // Stores count of odd elements int odd = 0 ; // Stores count of even elements int even = 0 ; // Stores the cost of partitions ArrayList<Integer> V = new ArrayList<Integer>(); for ( int i = 0 ; i < N - 1 ; i++) { // Odd element if (arr[i] % 2 == 1 ) { odd++; } // Even element else { even++; } // Partition is possible if (odd == even) { int cost = Math.abs(arr[i] - arr[i + 1 ]); // Append the cost of partition V.add(cost); } } // Stores the maximum number of // partitions int ans = 0 ; // Sort the costs in ascending order V.sort( null ); // Traverse the vector V for ( int i = 0 ; i < V.size(); i++) { // Check if cost is less than K if (V.get(i) <= K) { // Update the value of K K = K - V.get(i); // Update the value of ans ans++; } else { break ; } } // Return ans return ans; } // Driver code public static void main(String args[]) { // Given Input int arr[] = { 1 , 2 , 5 , 10 , 15 , 20 }; int N = arr.length; int K = 4 ; // Function call System.out.println(maximumcut(arr, N, K)); } } // This code is contributed by gfgking. |
Python3
# Python3 code for the above approach # Function to find the maximum # partitions of the array with # equal even and odd elements # with cost less than k def maximumcut(arr, N, K): # Stores count of odd elements odd = 0 # Stores count of even elements even = 0 # Stores the cost of partitions V = [] for i in range ( 0 , N - 1 , 1 ): # Odd element if (arr[i] % 2 = = 1 ): odd + = 1 # Even element else : even + = 1 # Partition is possible if (odd = = even): cost = abs (arr[i] - arr[i + 1 ]) # Append the cost of partition V.append(cost) # Stores the maximum number of # partitions ans = 0 # Sort the costs in ascending order V.sort() # Traverse the vector V for i in range ( len (V)): # Check if cost is less than K if (V[i] < = K): # Update the value of K K = K - V[i] # Update the value of ans ans + = 1 else : break # Return ans return ans # Driver code if __name__ = = '__main__' : # Given Input arr = [ 1 , 2 , 5 , 10 , 15 , 20 ] N = len (arr) K = 4 # Function call print (maximumcut(arr, N, K)) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# code for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the maximum // partitions of the array with // equal even and odd elements // with cost less than k static int maximumcut( int []arr, int N, int K) { // Stores count of odd elements int odd = 0; // Stores count of even elements int even = 0; // Stores the cost of partitions List< int > V = new List< int >(); for ( int i = 0; i < N - 1; i++) { // Odd element if (arr[i] % 2 == 1) { odd++; } // Even element else { even++; } // Partition is possible if (odd == even) { int cost = Math.Abs(arr[i] - arr[i + 1]); // Append the cost of partition V.Add(cost); } } // Stores the maximum number of // partitions int ans = 0; // Sort the costs in ascending order V.Sort(); // Traverse the vector V for ( int i = 0; i < V.Count; i++) { // Check if cost is less than K if (V[i] <= K) { // Update the value of K K = K - V[i]; // Update the value of ans ans++; } else { break ; } } // Return ans return ans; } // Driver code public static void Main() { // Given Input int []arr = { 1, 2, 5, 10, 15, 20 }; int N = arr.Length; int K = 4; // Function call Console.Write(maximumcut(arr, N, K)); } } // This code is contributed by ipg2016107 |
Javascript
<script> // JavaScript code for the above approach // Function to find the maximum // partitions of the array with // equal even and odd elements // with cost less than k function maximumcut(arr, N, K) { // Stores count of odd elements let odd = 0; // Stores count of even elements let even = 0; // Stores the cost of partitions var V = []; for (let i = 0; i < N - 1; i++) { // Odd element if (arr[i] % 2 == 1) { odd++; } // Even element else { even++; } // Partition is possible if (odd == even) { let cost = Math.abs(arr[i] - arr[i + 1]); // Append the cost of partition V.push(cost); } } // Stores the maximum number of // partitions let ans = 0; // Sort the costs in ascending order V.sort(); // Traverse the vector V for (let i = 0; i < V.length; i++) { // Check if cost is less than K if (V[i] <= K) { // Update the value of K K = K - V[i]; // Update the value of ans ans++; } else { break ; } } // Return ans return ans; } // Driver code // Given Input let arr = [1, 2, 5, 10, 15, 20]; let N = arr.length; let K = 4; // Function call document.write(maximumcut(arr, N, K)); // This code is contributed by Potta Lokesh </script> |
1
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)