Given an arr[] of length N, the task is to make parity of arr[] the same by using the below-provided operation:
- Select a subarray containing elements of the same parity.
- Remove the subarray.
- The cost to remove that subarray is (absolute adjacent difference of all elements present in sub-array)*(length of subarray). For a sub-array of length 1, the cost will be the element present in that subarray.
Examples:
Input: N = 3, arr[] = {2, 4, 6}
Output: 0
Explanation: All the elements of given arr[] are even, Input arr[] has even parity already. Therefore, minimum cost is 0Input: N = 4, arr[] = {22, 42, 64, 7}
Output: 7
Explanation: It will be optimal to remove sub-array {A4, . . . , A4} = {7}. Length of Sub-array is one, Therefore, minimum cost to remove this sub-array is = 7. After removing {7}, arr[] = {22, 42, 64}. it can be verified that now arr[] contains only even elements. Therefore, minimum cost to make parity of arr[] is 7.Input: N = 7, arr[] = {2, 3, 1, 5, 4, 6, 4}
Output: 14
Explanation: It will be optimal to make arr[] of odd parity.
First sub-array = {2}, Cost = 2
Second sub-array = {4, 6, 4}, cost = ( |6-4|+|4-6| )*(3) = (2+2)*(3) = 12
Hence, Total minimum cost will be 2+12=14. arr[] after removing both sub-arrays = {3, 1, 5}
Approach: Implement the idea below to solve the problem:
The problem is based on Greedy approach for finding minimum cost. Find all the sub-arrays of even and odd parity, Then calculate minimum cost for both in two different variables. Print the minimum between both costs.
Follow the illustration below for a better understanding:
Illustr:
Consider array arr[] = {2, 3, 1, 5, 4, 6, 4}
Let us make the parity of given arr[] odd and even one by one.
- Even parity arr[]: For making arr[] of even parity, We have to remove all sub-arrays having odd parity along with their cost. There is only one odd subarray present in arr[] from index 1 to 3.
- First odd sub-array = {3, 1, 5}. Cost for removing this sub-array = ( |1-3|+|5-1| )*(3) = 6*3=18
- arr[] after removing the subarray is {2, 4, 6, 4}. It can be verified that now arr[] have even parity having costs as 18.
- Odd parity arr[]: For making arr[] of odd parity, We have to remove all sub-arrays having even parity along with their cost. There are two even subarrays present in arr[] from index 0 to 0 and 4 to 6 respectively.
- First even sub-array = {2}. Cost for removing this sub-array = 2
- Second even sub-array = {4, 6, 4}. Cost for removing this sub-array = ( |6-4|+|4-6| )*(3) = 4*3 = 12
- arr[] after removing sub-arrays {1} and {4, 6, 4} is {1, 3, 5}. It can be verified that now arr[] have odd parity having costs as 2+12=14.
Now, We have test arr[] for both parities. The minimum cost will be min(cost for making arr[] parity even, cost for making arr[] parity odd).
Minimum cost = min(14, 18) = 14.
Follow the steps mentioned below to implement the idea:
- Consider two variables (Say min_cost_even and min_cost_odd) for holding minimum cost to make parity of arr[] odd or even respectively.
- Find all subarrays having odd parity, Calculate the cost of each sub-array and add it into min_cost_even.
- Find all sub-arrays having Even parity, Calculate the cost of each sub-array and add it into min_cost_odd.
- Return the minimum value between both costs obtained in steps 2 and 3 i.e., min(min_cost_odd, min_cost_even).
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function for finding minimum value // from two input arguments long mini( long a, long b) { return a <= b ? a : b; } // Function for returning minimum cost long minCost( int N, int arr[]) { // Variable to hold minimum cost, // to make arr[] parity even long min_cost_even = 0; // LeftEnd of arr[] initialized for finding // subarrays containing same parity elements int leftEnd = 0; // Variable to hold minimum cost, // to make arr[] parity odd long min_cost_odd = 0; // Algorithm to find Sub-arrays of Odd parity // according to 0 based indexing while (leftEnd < N) { if (arr[leftEnd] % 2 == 0) { leftEnd++; } else { int rightEnd = leftEnd; while (rightEnd < N - 1 && arr[rightEnd + 1] % 2 != 0) rightEnd = rightEnd + 1; // Condition When sub-array has length 1 if (leftEnd == rightEnd) { // Adding mincost to verify this // sub-array min_cost_even += arr[leftEnd]; } // When length is greater than 1 else { // Temporary variable to hold cost for // this sub-array long temp = 0; // Loop for traversing on subarray for ( int i = leftEnd + 1; i <= rightEnd; i++) { // Initializing temp with absolute // adjacent difference temp += ( abs (arr[i] - arr[i - 1])); } // Multiplying temp with subarray's // length temp *= (rightEnd - leftEnd + 1); // Adding temp's value to min_cost_even min_cost_even += temp; } // Incrementing leftEnd for finding next // subarray of odd parity leftEnd = rightEnd + 1; } } // Set leftEnd to 0, So that we can traverse again // on arr[] For finding even parity sub-arrays leftEnd = 0; // Algorithm to find Sub-arrays of Even parity // according to 0 based indexing while (leftEnd < N) { if (arr[leftEnd] % 2 != 0) { leftEnd++; } else { int rightEnd = leftEnd; while (rightEnd < N - 1 && arr[rightEnd + 1] % 2 == 0) rightEnd = rightEnd + 1; // If sub-array is of length 1 if (leftEnd == rightEnd) { // Adding cost to min_cost_odd variable min_cost_odd += arr[leftEnd]; } // When sub-array has length greater than 1 else { // Temp variable to hold cost for this // even parity sub-array long temp = 0; // Loop for traversing on sub-array for ( int i = leftEnd + 1; i <= rightEnd; i++) { // Adding absolute adjacent // difference to temp temp += ( abs (arr[i] - arr[i - 1])); } // Multiplying temp with length of // sub-array temp *= (rightEnd - leftEnd + 1); // Adding temp value to min_cost_odd min_cost_odd += temp; } // Incrementing leftEnd for finding next // Even parity sub-array leftEnd = rightEnd + 1; } } // Returning minimum cost return mini(min_cost_odd, min_cost_even); } int main() { // Testcase1 int N = 7; int arr[] = { 2, 3, 1, 5, 4, 6, 4 }; // Function call cout << (minCost(N, arr)) << endl; // Testcase2 int N2 = 5; int arr2[] = { 1, 2, 3, 5, 4 }; // Function call cout << (minCost(N2, arr2)) << endl; return 0; } // This code is contributed by ksam24000 |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Driver Function public static void main(String[] args) { // Testcase1 int N = 7 ; int [] arr = { 2 , 3 , 1 , 5 , 4 , 6 , 4 }; // Function call System.out.println(minCost(N, arr)); // Testcase2 int N2 = 5 ; int [] arr2 = { 1 , 2 , 3 , 5 , 4 }; // Function call System.out.println(minCost(N2, arr2)); } // Function for returning minimum cost static long minCost( int N, int [] arr) { // Variable to hold minimum cost, // to make arr[] parity even long min_cost_even = 0 ; // LeftEnd of arr[] initialized for finding // subarrays containing same parity elements int leftEnd = 0 ; // Variable to hold minimum cost, // to make arr[] parity odd long min_cost_odd = 0 ; // Algorithm to find Sub-arrays of Odd parity // according to 0 based indexing while (leftEnd < N) { if (arr[leftEnd] % 2 == 0 ) { leftEnd++; } else { int rightEnd = leftEnd; while (rightEnd < N - 1 && arr[rightEnd + 1 ] % 2 != 0 ) rightEnd = rightEnd + 1 ; // Condition When sub-array has length 1 if (leftEnd == rightEnd) { // Adding mincost to verify this // sub-array min_cost_even += arr[leftEnd]; } // When length is greater than 1 else { // Temporary variable to hold cost for // this sub-array long temp = 0 ; // Loop for traversing on subarray for ( int i = leftEnd + 1 ; i <= rightEnd; i++) { // Initializing temp with absolute // adjacent difference temp += (Math.abs(arr[i] - arr[i - 1 ])); } // Multiplying temp with subarray's // length temp *= (rightEnd - leftEnd + 1 ); // Adding temp's value to min_cost_even min_cost_even += temp; } // Incrementing leftEnd for finding next // subarray of odd parity leftEnd = rightEnd + 1 ; } } // Set leftEnd to 0, So that we can traverse again // on arr[] For finding even parity sub-arrays leftEnd = 0 ; // Algorithm to find Sub-arrays of Even parity // according to 0 based indexing while (leftEnd < N) { if (arr[leftEnd] % 2 != 0 ) { leftEnd++; } else { int rightEnd = leftEnd; while (rightEnd < N - 1 && arr[rightEnd + 1 ] % 2 == 0 ) rightEnd = rightEnd + 1 ; // If sub-array is of length 1 if (leftEnd == rightEnd) { // Adding cost to min_cost_odd variable min_cost_odd += arr[leftEnd]; } // When sub-array has length greater than 1 else { // Temp variable to hold cost for this // even parity sub-array long temp = 0 ; // Loop for traversing on sub-array for ( int i = leftEnd + 1 ; i <= rightEnd; i++) { // Adding absolute adjacent // difference to temp temp += (Math.abs(arr[i] - arr[i - 1 ])); } // Multiplying temp with length of // sub-array temp *= (rightEnd - leftEnd + 1 ); // Adding temp value to min_cost_odd min_cost_odd += temp; } // Incrementing leftEnd for finding next // Even parity sub-array leftEnd = rightEnd + 1 ; } } // Returning minimum cost return min(min_cost_odd, min_cost_even); } // Function for finding minimum value // from two input arguments static long min( long a, long b) { return a <= b ? a : b; } } |
Python3
# Python code to implement the approach # Function for finding minimum value # from two input arguments def Min (a, b): return a if a < = b else b # Function for returning minimum cost def minCost(N, arr): # Variable to hold minimum cost, # to make arr[] parity even min_cost_even = 0 # LeftEnd of arr[] initialized for finding # subarrays containing same parity elements leftEnd = 0 # Variable to hold minimum cost, # to make arr[] parity odd min_cost_odd = 0 # Algorithm to find Sub-arrays of Odd parity # according to 0 based indexing while (leftEnd < N): if (arr[leftEnd] % 2 = = 0 ): leftEnd + = 1 else : rightEnd = leftEnd while (rightEnd < N - 1 and arr[rightEnd + 1 ] % 2 ! = 0 ): rightEnd = rightEnd + 1 # Condition When sub-array has length 1 if (leftEnd = = rightEnd): # Adding mincost to verify this sub-array min_cost_even = min_cost_even + arr[leftEnd] # when length is greater than 1 else : # Temporary variable to hold cost for this sub-array temp = 0 # Loop for traversing on subarray for i in range (leftEnd + 1 , rightEnd + 1 ): # Initializing temp with absolute adjacent difference temp = temp + abs (arr[i] - arr[i - 1 ]) # Multiplying temp with subarray's length temp = temp * (rightEnd - leftEnd + 1 ) # Adding temp's value to min_cost_even min_cost_even = min_cost_even + temp # Incrementing leftEnd for finding next # subarray of odd parity leftEnd = rightEnd + 1 # Set leftEnd to 0, So that we can traverse again # on arr[] For finding even parity sub-arrays leftEnd = 0 # Algorithm to find Sub-arrays of Even parity # according to 0 based indexing while (leftEnd < N): if (arr[leftEnd] % 2 ! = 0 ): leftEnd + = 1 else : rightEnd = leftEnd while (rightEnd < N - 1 and arr[rightEnd + 1 ] % 2 = = 0 ): rightEnd = rightEnd + 1 # If sub-array is of length 1 if (leftEnd = = rightEnd): # Adding cost to min_cost_odd variable min_cost_odd = min_cost_odd + arr[leftEnd] # When sub-array has length greater than 1 else : # Temp variable to hold cost for this even parity sub-array temp = 0 # loop for traversing on sub-array for i in range (leftEnd + 1 , rightEnd + 1 ): # Adding absolute adjacent difference to temp temp = temp + abs (arr[i] - arr[i - 1 ]) # Multiplying temp with length of sub-array temp = temp * (rightEnd - leftEnd + 1 ) # Adding temp value to min_cost_odd min_cost_odd = min_cost_odd + temp # Incrementing leftEnd for finding next # Even parity sub-array leftEnd = rightEnd + 1 # Returning minimum cost return Min (min_cost_odd, min_cost_even) # Testcase1 N = 7 arr = [ 2 , 3 , 1 , 5 , 4 , 6 , 4 ] # Function call print (minCost(N, arr)) # Testcase2 N2 = 5 arr2 = [ 1 , 2 , 3 , 5 , 4 ] # Function call print (minCost(N2, arr2)) # This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approach using System; public class GFG { static public void Main() { // Testcase1 int N = 7; int [] arr = { 2, 3, 1, 5, 4, 6, 4 }; // Function call Console.WriteLine(minCost(N, arr)); // Testcase2 int N2 = 5; int [] arr2 = { 1, 2, 3, 5, 4 }; // Function call Console.WriteLine(minCost(N2, arr2)); } // Function for returning minimum cost static long minCost( int N, int [] arr) { // Variable to hold minimum cost, // to make arr[] parity even long min_cost_even = 0; // LeftEnd of arr[] initialized for finding // subarrays containing same parity elements int leftEnd = 0; // Variable to hold minimum cost, // to make arr[] parity odd long min_cost_odd = 0; // Algorithm to find Sub-arrays of Odd parity // according to 0 based indexing while (leftEnd < N) { if (arr[leftEnd] % 2 == 0) { leftEnd++; } else { int rightEnd = leftEnd; while (rightEnd < N - 1 && arr[rightEnd + 1] % 2 != 0) rightEnd = rightEnd + 1; // Condition When sub-array has length 1 if (leftEnd == rightEnd) { // Adding mincost to verify this // sub-array min_cost_even += arr[leftEnd]; } // When length is greater than 1 else { // Temporary variable to hold cost for // this sub-array long temp = 0; // Loop for traversing on subarray for ( int i = leftEnd + 1; i <= rightEnd; i++) { // Initializing temp with absolute // adjacent difference temp += (Math.Abs(arr[i] - arr[i - 1])); } // Multiplying temp with subarray's // length temp *= (rightEnd - leftEnd + 1); // Adding temp's value to min_cost_even min_cost_even += temp; } // Incrementing leftEnd for finding next // subarray of odd parity leftEnd = rightEnd + 1; } } // Set leftEnd to 0, So that we can traverse again // on arr[] For finding even parity sub-arrays leftEnd = 0; // Algorithm to find Sub-arrays of Even parity // according to 0 based indexing while (leftEnd < N) { if (arr[leftEnd] % 2 != 0) { leftEnd++; } else { int rightEnd = leftEnd; while (rightEnd < N - 1 && arr[rightEnd + 1] % 2 == 0) rightEnd = rightEnd + 1; // If sub-array is of length 1 if (leftEnd == rightEnd) { // Adding cost to min_cost_odd variable min_cost_odd += arr[leftEnd]; } // When sub-array has length greater than 1 else { // Temp variable to hold cost for this // even parity sub-array long temp = 0; // Loop for traversing on sub-array for ( int i = leftEnd + 1; i <= rightEnd; i++) { // Adding absolute adjacent // difference to temp temp += (Math.Abs(arr[i] - arr[i - 1])); } // Multiplying temp with length of // sub-array temp *= (rightEnd - leftEnd + 1); // Adding temp value to min_cost_odd min_cost_odd += temp; } // Incrementing leftEnd for finding next // Even parity sub-array leftEnd = rightEnd + 1; } } // Returning minimum cost return min(min_cost_odd, min_cost_even); } // Function for finding minimum value // from two input arguments static long min( long a, long b) { return a <= b ? a : b; } } // This code is contributed by lokeshmvs21. |
Javascript
// JavaScript code for the above approach // Function for returning minimum cost function minCost(N, arr) { // Variable to hold minimum cost, // to make arr[] parity even let min_cost_even = 0; // LeftEnd of arr[] initialized for finding // subarrays containing same parity elements let leftEnd = 0; // Variable to hold minimum cost, // to make arr[] parity odd let min_cost_odd = 0; // Algorithm to find Sub-arrays of Odd parity // according to 0 based indexing while (leftEnd < N) { if (arr[leftEnd] % 2 == 0) { leftEnd++; } else { let rightEnd = leftEnd; while (rightEnd < N - 1 && arr[rightEnd + 1] % 2 != 0) rightEnd = rightEnd + 1; // Condition When sub-array has length 1 if (leftEnd == rightEnd) { // Adding mincost to verify this // sub-array min_cost_even += arr[leftEnd]; } // When length is greater than 1 else { // Temporary variable to hold cost for // this sub-array let temp = 0; // Loop for traversing on subarray for (let i = leftEnd + 1; i <= rightEnd; i++) { // Initializing temp with absolute // adjacent difference temp += (Math.abs(arr[i] - arr[i - 1])); } // Multiplying temp with subarray's // length temp *= (rightEnd - leftEnd + 1); // Adding temp's value to min_cost_even min_cost_even += temp; } // Incrementing leftEnd for finding next // subarray of odd parity leftEnd = rightEnd + 1; } } // Set leftEnd to 0, So that we can traverse again // on arr[] For finding even parity sub-arrays leftEnd = 0; // Algorithm to find Sub-arrays of Even parity // according to 0 based indexing while (leftEnd < N) { if (arr[leftEnd] % 2 != 0) { leftEnd++; } else { let rightEnd = leftEnd; while (rightEnd < N - 1 && arr[rightEnd + 1] % 2 == 0) rightEnd = rightEnd + 1; // If sub-array is of length 1 if (leftEnd == rightEnd) { // Adding cost to min_cost_odd variable min_cost_odd += arr[leftEnd]; } // When sub-array has length greater than 1 else { // Temp variable to hold cost for this // even parity sub-array let temp = 0; // Loop for traversing on sub-array for (let i = leftEnd + 1; i <= rightEnd; i++) { // Adding absolute adjacent // difference to temp temp += (Math.abs(arr[i] - arr[i - 1])); } // Multiplying temp with length of // sub-array temp *= (rightEnd - leftEnd + 1); // Adding temp value to min_cost_odd min_cost_odd += temp; } // Incrementing leftEnd for finding next // Even parity sub-array leftEnd = rightEnd + 1; } } // Returning minimum cost return min(min_cost_odd, min_cost_even); } // Function for finding minimum value // from two input arguments function min(a, b) { return a <= b ? a : b; } // Driver Function // Testcase1 let N = 7; let arr = [2, 3, 1, 5, 4, 6, 4]; // Function call console.log(minCost(N, arr) + "<br>" ); // Testcase2 let N2 = 5; let arr2 = [1, 2, 3, 5, 4]; // Function call console.log(minCost(N2, arr2)); // This code is contributed by Potta Lokesh |
14 5
Time Complexity: O(N)
Auxiliary Space: No extra space is used.
Related Articles:
- Introduction to Arrays – Data Structure and Algorithm Tutorials
- Introduction to Greedy Algorithm – Data Structures and Algorithm Tutorials
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!