Given an array arr[] of size N and two integers X and Y, the task is to find the minimum cost required to modify the array such that even indices have even elements and odd indices have odd elements on them, either by swapping two elements of the array with a cost of X or by incrementing or decrementing 1 from the element with a cost of Y.
Examples:
Input: arr[] = {5, 3, 7, 2, 1}, X = 1, Y = 2
Output: 5
Explanation:
Following are the operations performed:
Operation 1: Swap the array elements at indices 0 and 3, modifies the array to {2, 3, 7, 5, 1}. The cost of this operations is X(= 1).
Operation 2: Incrementing the array elements at index 2, modifies the array to {2, 3, 8, 5, 1}. The cost of this operations is Y(= 2).
Operation 3: Incrementing the array elements at index 4, modifies the array to {2, 3, 8, 5, 2}. The cost of this operations is Y(= 2).
Therefore, the total cost is 1 + 2 + 2 = 5, which is minimum.
Input: arr[] = {1, 2, 3, 4}, X = 1, Y = 2
Output: 2
Approach: The given problem can be solved by using the following observations by first finding the count of elements that are wrongly placed at odd and even indices as oddCount and evenCount respectively:
- Case 1: The cost can be calculated by performing the swap operations on a minimum of oddCount and evenCount at a cost of X and performing the decrementing operation on the remaining elements at a cost of Y.
- Case 2: The cost can be calculated by performing the decrementing operation on the remaining elements at a cost of Y.
The minimum of the costs obtained in the above two cases is the required result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum cost to// modify the array according to the// given criteriaint minimumCost(int arr[], int N, int X, int Y){ // Count of wrong positioned odd // and even elements int even_count = 0, odd_count = 0; for (int i = 0; i < N; i++) { // Odd Count if ((arr[i] & 1) && (i % 2 == 0)) { odd_count++; } // Even Count if ((arr[i] % 2) == 0 && (i & 1)) { even_count++; } } // Cost for Case 1 // Swapping Cost int cost1 = X * min(odd_count, even_count); // Decrementing cost after swapping int cost2 = Y * (max(odd_count, even_count) - min(odd_count, even_count)); // Cost for Case 2 // Only decrementing cost int cost3 = (odd_count + even_count) * Y; // Return the minimum cost of the // two cases return min(cost1 + cost2, cost3);}// Driver Codeint main(){ int arr[] = { 5, 3, 7, 2, 1 }, X = 10, Y = 2; int N = sizeof(arr) / sizeof(arr[0]); cout << minimumCost(arr, N, X, Y); return 0;} |
Java
// Java program for the above approachclass GFG { // Function to find the minimum cost to // modify the array according to the // given criteria public static int minimumCost(int arr[], int N, int X, int Y) { // Count of wrong positioned odd // and even elements int even_count = 0, odd_count = 0; for (int i = 0; i < N; i++) { // Odd Count if ((arr[i] & 1) > 0 && (i % 2 == 0)) { odd_count++; } // Even Count if ((arr[i] % 2) == 0 && (i & 1) > 0) { even_count++; } } // Cost for Case 1 // Swapping Cost int cost1 = X * Math.min(odd_count, even_count); // Decrementing cost after swapping int cost2 = Y * (Math.max(odd_count, even_count) - Math.min(odd_count, even_count)); // Cost for Case 2 // Only decrementing cost int cost3 = (odd_count + even_count) * Y; // Return the minimum cost of the // two cases return Math.min(cost1 + cost2, cost3); } // Driver Code public static void main(String args[]) { int arr[] = { 5, 3, 7, 2, 1 }, X = 10, Y = 2; int N = arr.length; System.out.println(minimumCost(arr, N, X, Y)); }}// This code is contributed by gfgking. |
Python3
# python program for the above approach# Function to find the minimum cost to# modify the array according to the# given criteriadef minimumCost(arr, N, X, Y): # Count of wrong positioned odd # and even elements even_count = 0 odd_count = 0 for i in range(0, N): # Odd Count if ((arr[i] & 1) and (i % 2 == 0)): odd_count += 1 # Even Count if ((arr[i] % 2) == 0 and (i & 1)): even_count += 1 # Cost for Case 1 # Swapping Cost cost1 = X * min(odd_count, even_count) # Decrementing cost after swapping cost2 = Y * (max(odd_count, even_count) - min(odd_count, even_count)) # Cost for Case 2 # Only decrementing cost cost3 = (odd_count + even_count) * Y # Return the minimum cost of the # two cases return min(cost1 + cost2, cost3)# Driver Codeif __name__ == "__main__": arr = [5, 3, 7, 2, 1] X = 10 Y = 2 N = len(arr) print(minimumCost(arr, N, X, Y)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;public class GFG { // Function to find the minimum cost to // modify the array according to the // given criteria public static int minimumCost(int []arr, int N, int X, int Y) { // Count of wrong positioned odd // and even elements int even_count = 0, odd_count = 0; for (int i = 0; i < N; i++) { // Odd Count if ((arr[i] & 1) > 0 && (i % 2 == 0)) { odd_count++; } // Even Count if ((arr[i] % 2) == 0 && (i & 1) > 0) { even_count++; } } // Cost for Case 1 // Swapping Cost int cost1 = X * Math.Min(odd_count, even_count); // Decrementing cost after swapping int cost2 = Y * (Math.Max(odd_count, even_count) - Math.Min(odd_count, even_count)); // Cost for Case 2 // Only decrementing cost int cost3 = (odd_count + even_count) * Y; // Return the minimum cost of the // two cases return Math.Min(cost1 + cost2, cost3); } // Driver Code public static void Main(string []args) { int []arr= { 5, 3, 7, 2, 1 }; int X = 10, Y = 2; int N = arr.Length; Console.WriteLine(minimumCost(arr, N, X, Y)); }}// This code is contributed by rutvik_56. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the minimum cost to // modify the array according to the // given criteria function minimumCost(arr, N, X, Y) { // Count of wrong positioned odd // and even elements let even_count = 0, odd_count = 0; for (let i = 0; i < N; i++) { // Odd Count if ((arr[i] & 1) && (i % 2 == 0)) { odd_count++; } // Even Count if ((arr[i] % 2) == 0 && (i & 1)) { even_count++; } } // Cost for Case 1 // Swapping Cost let cost1 = X * Math.min(odd_count, even_count); // Decrementing cost after swapping let cost2 = Y * (Math.max(odd_count, even_count) - Math.min(odd_count, even_count)); // Cost for Case 2 // Only decrementing cost let cost3 = (odd_count + even_count) * Y; // Return the minimum cost of the // two cases return Math.min(cost1 + cost2, cost3); } // Driver Code let arr = [5, 3, 7, 2, 1], X = 10, Y = 2; let N = arr.length; document.write(minimumCost(arr, N, X, Y));// This code is contributed by Potta Lokesh </script> |
Output:
8
Time Complexity: O(N)
Auxiliary Space: O(1)
