Given an input array, the task is to convert the given array into an ‘even array’. An even array is an array where every number is an even number. For making an array even you can do these two operations:
- If the current number is odd, then calculate the price to make the number even. For making a number even, you can swap adjacent positions with one position as even and another as odd.
Cost = the total number of swaps made. - If you want to delete the current element from the array then the cost will be 5.
Examples:
Input: {1243, 267, 2315}
Output: 5
Explanation: For making 1243 an even number, we will swap 4 and 3. This will cost 1 operation.
For making 267 an even number, we will swap 6 and 7. This will cost 1 operation.
For making 2315 an even number, we will swap 2 and 3 followed by 2 and 1, and then 2 and 5. This will cost 3 operations.
So the minimum cost will be 5.Input: {12, 23, 2171315}
Output: 6
Explanation: 12 is already an even number so it will cost 0 operations.
For making 23 an even number, we will swap 2 and 3. This will cost 1 operation.
For making 2171315 an even number, we need to perform 6 operations so instead of making it even we will delete it from the array which will cost 5 operations.
So after deleting, the minimum cost will be 6.
Approach: To solve the problem follow the below idea:
The idea is to maintain a variable for calculating the minimum cost and for every single element of the array choose the minimum between 5 or the total number of swaps required.
This entire thing can be done by following the below-mentioned steps:
- Implement a function named makeEven which takes an integer as an input and returns the number of swaps required for making that number even or -1 if there is no even digit in that number.
- Initialize a variable minCost for storing the minimum cost and iterate over the input array.
- For every single iteration, Initialize a variable cost = makeEven ( currentElement).
- if cost == -1 then add 5 to minCost otherwise add minimum among 5 and cost to minCost.
- return minCost.
Below is the implementation for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int makeEven(int n){ int cost = 0; // For calculating the cost for making // the number even while (n % 2 != 0) { // While loop till the number // becomes even n /= 10; // The last digit is odd so we // remove it to check next digit // and increment the cost by one. cost++; } if (n == 0) return -1; return cost;}int makeArrayEven(vector<int> arr){ int minCost = 0; for (int i = 0; i < arr.size(); i++) { int cost = makeEven(arr[i]); // Function call for // makeEven function if (cost != -1) minCost += min(5, cost); // If current element can be // converted into even number else minCost += 5; // If current element cannot be // converted into even number // this means we have to delete // current element which cost 5 } return minCost;}// Driver's codeint main(){ vector<int> arr{ 12, 23, 2171315 }; // Function call cout << makeArrayEven(arr); return 0;} |
Java
// Java code for the above approach:import java.io.*;class GFG { static int makeEven(int n) { int cost = 0; // For calculating the cost for making the number // even while (n % 2 != 0) { // While loop till the number becomes even n /= 10; // The last digit is odd so we remove it to // check next digit and increment the cost by // one. cost++; } if (n == 0) return -1; return cost; } static int makeArrayEven(int[] arr) { int minCost = 0; for (int i = 0; i < arr.length; i++) { int cost = makeEven(arr[i]); // Function call for makeEven function if (cost != -1) minCost += Math.min(5, cost); // If current element can be converted into even // number else minCost += 5; // If current element cannot be converted into // even number this means we have to delete // current element which cost 5 } return minCost; } public static void main(String[] args) { int[] arr = { 12, 23, 2171315 }; // Function call System.out.println(makeArrayEven(arr)); }}// This code is contributed lokesh. |
Python
def makeEven(n): cost = 0 # For calculating the cost for making # the number even while n % 2 != 0: # While loop till the number # becomes even n //= 10 # The last digit is odd so we # remove it to check next digit # and increment the cost by one. cost += 1 if n == 0: return -1 return costdef makeArrayEven(arr): minCost = 0 for i in range(len(arr)): cost = makeEven(arr[i]) # Function call for # makeEven function if cost != -1: minCost += min(5, cost) # If current element can be # converted into even number else: minCost += 5 # If current element cannot be # converted into even number # this means we have to delete # current element which cost 5 return minCost# Driver's codearr = [12, 23, 2171315]# Function callprint(makeArrayEven(arr)) |
C#
using System;using System.Collections.Generic;class GFG { static int makeEven(int n) { int cost = 0; // For calculating the cost for making // the number even while (n % 2 != 0) { // While loop till the number // becomes even n /= 10; // The last digit is odd so we // remove it to check next digit // and increment the cost by one. cost++; } if (n == 0) return -1; return cost; } static int makeArrayEven(List<int> arr) { int minCost = 0; for (int i = 0; i < arr.Count; i++) { int cost = makeEven(arr[i]); // Function call for // makeEven function if (cost != -1) minCost += Math.Min(5, cost); // If current element can be // converted into even number else minCost += 5; // If current element cannot be // converted into even number // this means we have to delete // current element which cost 5 } return minCost; } static void Main(string[] args) { List<int> arr = new List<int>{ 12, 23, 2171315 }; // Function call Console.WriteLine(makeArrayEven(arr)); }} |
Javascript
<script> function makeEven(n) { let cost = 0; // For calculating the cost for making // the number even while (n % 2 !== 0) { // While loop till the number // becomes even n = Math.floor(n / 10); // The last digit is odd so we // remove it to check next digit // and increment the cost by one. cost++; } if (n === 0) return -1; return cost; } function makeArrayEven(arr) { let minCost = 0; for (let i = 0; i < arr.length; i++) { const cost = makeEven(arr[i]); // Function call for // makeEven function if (cost !== -1) minCost += Math.min(5, cost); // If current element can be // converted into even number else minCost += 5; // If current element cannot be // converted into even number // this means we have to delete // current element which cost 5 } return minCost; } // Driver's code const arr = [12, 23, 2171315]; // Function call console.log(makeArrayEven(arr));</script> |
Output
6
Time Complexity: O(N), where N is the size of the array,
Auxiliary Space: O(1)
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!
