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 argumentslong mini(long a, long b) { return a <= b ? a : b; }// Function for returning minimum costlong 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 approachimport 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 argumentsdef Min(a, b): return a if a <= b else b# Function for returning minimum costdef 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)# Testcase1N = 7arr = [2, 3, 1, 5, 4, 6, 4]# Function callprint(minCost(N, arr))# Testcase2N2 = 5arr2 = [1, 2, 3, 5, 4]# Function callprint(minCost(N2, arr2))# This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approachusing 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 |
Output
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
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!
Share your thoughts in the comments
