Given an arr[] of length N containing positive elements. the task is to make arr[] sum even using minimum operations. In an operation, you can select any element arr[i] for(1 ? i ? N) of arr[] and convert arr[i] into power(arr[i],j), Where j = max(0, (arr[i] / 2) – 1).
Examples:
Input: N = 4, arr[] = {1, 4, 6, 3}
Output: 0
Explanation: The sum of arr[] is: 1 + 4 + 6 + 3 = 14, Which is already even. Therefore, no operations are required to perform.Input: N = 3, arr[] = {1, 1, 1}
Output: -1
Explanation: It can be verified that performing any number of operations on any element can’t make the sum of arr[] even.
Approach: Implement the idea below to solve the problem:
- It can be observed that by the given operation only 2 can be converted into 1, Which is a change from even parity to odd parity. No other any element can change its parity from even to odd or odd to even by using above given operation.
- This idea gives us concept that if the sum of arr[] is already even, Then 0 operation is required.
- If arr[] sum is odd, Then sum can be converted into even only and only if at least one time 2 is present in the arr[] else sum can’t be made even in any number of operations and return -1.
Follow the below steps to implement the idea:
- Initialize sum = 0, to calculate the sum of all the elements in arr[].
- Maintain a flag that is initially false, when 2 occurs in arr[] change it to true.
- If the sum is already even, return 0.
- If the sum is odd, then:
- If flag = true, return 1, which is the minimum number of operations required.
- If flag = false, return -1, not possible to make the sum even.
Below is the code to implement the approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to calculate Minimum Operation// required to make sum evenvoid minOperations(int N, int arr[]){ // Initialize sum = 0 long sum = 0; // Flag for checking if there is 2 // present or not in arr[] atleast once bool flag = false; // Loop for traversing on arr[] for (int i = 0; i < N; i++) { // Adding current element of // arr[] in sum variable sum += arr[i]; // When current element of // arr[] is equal to two if (arr[i] == 2) { // Marking flag as true flag = true; } } // Condition, When sum is odd if (sum % 2 == 0) { // Printing 0 as output cout << "0" << endl; } // Condition to check flag is // true or not else if (flag) { // Printing Minimum operations // required Which is 1 cout << "1" << endl; } // If 2 is not present in arr and sum // is also not even else { // Printing -1 as output cout << "-1" << endl; }}int main() { // Testcase 1 int N = 4; int arr[] = { 1, 1, 1, 2 }; // Function call minOperations(N, arr); // Testcase 2 int N2 = 5; int arr2[] = { 9, 4, 6, 3, 7 }; // Function call minOperations(N2, arr2); return 0;}// This code is contributed by rahulbhardwaj0711 |
Java
// Java code to implement the approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Driver code public static void main(String[] args) throws java.lang.Exception { // Testcase 1 int N = 4; int arr[] = { 1, 1, 1, 2 }; // Function call minOperations(N, arr); // Testcase 2 int N2 = 5; int arr2[] = { 9, 4, 6, 3, 7 }; // Function call minOperations(N2, arr2); } // Function to calculate Minimum Operation // required to make sum even static void minOperations(int N, int arr[]) { // Initialize sum = 0 long sum = 0; // Flag for checking if there is 2 // is present or not in arr[] at // least once boolean flag = false; // Loop for traversing on arr[] for (int i = 0; i < N; i++) { // Adding current element of // arr[] in sum variable sum += arr[i]; // When current element of // arr[] is equal to two if (arr[i] == 2) { // Marking flag as true flag = true; } } // Condition, When sum is odd if (sum % 2 == 0) { // Printing 0 as output System.out.println(0); } // Condition to check flag is // true or not else if (flag) { // Printing Minimum operations // required Which is 1 System.out.println(1); } // If 2 is not present in arr[] and sum // is also not even else { // Printing -1 as output System.out.println(-1); } }} |
Python3
def min_operations(N, arr): # Initialize sum to 0 sum = 0 # Flag for checking if there is a 2 in arr at least once flag = False # Loop through arr for i in range(N): # Add current element of arr to sum sum += arr[i] # Check if current element of arr is 2 if arr[i] == 2: flag = True # If sum is even if sum % 2 == 0: # Print 0 print(0) # If flag is true elif flag: # Print 1 print(1) # If 2 is not present in arr and sum is not even else: # Print -1 print(-1)# Test case 1N1 = 4arr1 = [1, 1, 1, 2]# Function callmin_operations(N1, arr1)# Test case 2N2 = 5arr2 = [9, 4, 6, 3, 7]# Function callmin_operations(N2, arr2)#This code is contributed by sanjanasikarwar24 |
C#
using System;namespace GFG{ class Program { static void Main(string[] args) { // Test case 1 int N1 = 4; int[] arr1 = { 1, 1, 1, 2 }; // Function call MinOperations(N1, arr1); // Test case 2 int N2 = 5; int[] arr2 = { 9, 4, 6, 3, 7 }; // Function call MinOperations(N2, arr2); } // Function to calculate Minimum Operation required to make sum even static void MinOperations(int N, int[] arr) { // Initialize sum to 0 long sum = 0; // Flag for checking if there is a 2 in arr at least once bool flag = false; // Loop through arr for (int i = 0; i < N; i++) { // Add current element of arr to sum sum += arr[i]; // Check if current element of arr is 2 if (arr[i] == 2) { flag = true; } } // If sum is even if (sum % 2 == 0) { // Print 0 Console.WriteLine(0); } // If flag is true else if (flag) { // Print 1 Console.WriteLine(1); } // If 2 is not present in arr and sum is not even else { // Print -1 Console.WriteLine(-1); } } }}//This code is contributed by sanjanasikarwar24 |
Javascript
// Function to calculate Minimum Operation required to make sum evenfunction minOperations(N, arr) { // Initialize sum to 0 let sum = 0; // Flag for checking if there is a 2 in arr at least once let flag = false; // Loop through arr for (let i = 0; i < N; i++) { // Add current element of arr to sum sum += arr[i]; // Check if current element of arr is 2 if (arr[i] === 2) { flag = true; } } // If sum is even if (sum % 2 === 0) { // Print 0 console.log(0); } // If flag is true else if (flag) { // Print 1 console.log(1); } // If 2 is not present in arr and sum is not even else { // Print -1 console.log(-1); }}// Test case 1let N1 = 4;let arr1 = [1, 1, 1, 2];// Function callminOperations(N1, arr1);// Test case 2let N2 = 5;let arr2 = [9, 4, 6, 3, 7];// Function callminOperations(N2, arr2);//This code is contributed by sanjanasikarwar24 |
Output
1 -1
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Articles:
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
