Given an array arr[] consisting of N positive integers, the task is to make all array elements even by replacing any pair of array elements with their sum.
Examples:
Input: arr[] = {5, 6, 3, 7, 20}
Output: 3
Explanation:
Operation 1: Replace arr[0] and arr[2] by their sum ( = 5 + 3 = 8) modifies arr[] to {8, 6, 8, 7, 20}.
Operation 2: Replace arr[2] and arr[3] by their sum ( = 7 + 8 = 15) modifies arr[] to {8, 6, 15, 15, 20}.
Operation 3: Replace arr[2] and arr[3] by their sum ( = 15 + 15 = 30) modifies arr[] to {8, 6, 30, 30, 20}.Input: arr[] = {2, 4, 16, 8, 7, 9, 3, 1}
Output: 2
Approach: The idea is to keep replacing two odd array elements by their sum until all array elements are even. Follow the steps below to solve the problem:
- Initialize a variable, say moves, to store the minimum number of replacements required.
- Calculate the total number of odd elements present in the given array and store it in a variable, say cnt.
- If the value of cnt is odd, then print (cnt / 2 + 2) as the result. Otherwise, print cnt / 2 as the 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 number// of replacements required to make// all array elements evenvoid minMoves(int arr[], int N){ // Stores the count of odd elements int odd_element_cnt = 0; // Traverse the array for (int i = 0; i < N; i++) { // Increase count of odd elements if (arr[i] % 2 != 0) { odd_element_cnt++; } } // Store number of replacements required int moves = (odd_element_cnt) / 2; // Two extra moves will be required // to make the last odd element even if (odd_element_cnt % 2 != 0) moves += 2; // Print the minimum replacements cout << moves;}// Driver Codeint main(){ int arr[] = { 5, 6, 3, 7, 20 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call minMoves(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the minimum number// of replacements required to make// all array elements evenstatic void minMoves(int arr[], int N){ // Stores the count of odd elements int odd_element_cnt = 0; // Traverse the array for (int i = 0; i < N; i++) { // Increase count of odd elements if (arr[i] % 2 != 0) { odd_element_cnt++; } } // Store number of replacements required int moves = (odd_element_cnt) / 2; // Two extra moves will be required // to make the last odd element even if (odd_element_cnt % 2 != 0) moves += 2; // Print the minimum replacements System.out.print(moves);}// Driver Codepublic static void main(String[] args){ int arr[] = { 5, 6, 3, 7, 20 }; int N = arr.length; // Function call minMoves(arr, N);}}// This code is contributed by shikhasingrajput |
C#
// C# program for the above approachusing System;public class GFG{ // Function to find the minimum number // of replacements required to make // all array elements even static void minMoves(int []arr, int N) { // Stores the count of odd elements int odd_element_cnt = 0; // Traverse the array for (int i = 0; i < N; i++) { // Increase count of odd elements if (arr[i] % 2 != 0) { odd_element_cnt++; } } // Store number of replacements required int moves = (odd_element_cnt) / 2; // Two extra moves will be required // to make the last odd element even if (odd_element_cnt % 2 != 0) moves += 2; // Print the minimum replacements Console.Write(moves); } // Driver Code public static void Main(String[] args) { int []arr = { 5, 6, 3, 7, 20 }; int N = arr.Length; // Function call minMoves(arr, N); }}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach# Function to find the minimum number# of replacements required to make# all array elements evendef minMoves(arr, N): # Stores the count of odd elements odd_element_cnt = 0; # Traverse the array for i in range(N): # Increase count of odd elements if (arr[i] % 2 != 0): odd_element_cnt += 1; # Store number of replacements required moves = (odd_element_cnt) // 2; # Two extra moves will be required # to make the last odd element even if (odd_element_cnt % 2 != 0): moves += 2; # Print the minimum replacements print(moves);# Driver Codeif __name__ == '__main__': arr = [5, 6, 3, 7, 20]; N = len(arr); # Function call minMoves(arr, N); # This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program for the above approach// Function to find the minimum number// of replacements required to make// all array elements evenfunction minMoves(arr, N){ // Stores the count of odd elements var odd_element_cnt = 0; var i; // Traverse the array for(i = 0; i < N; i++) { // Increase count of odd elements if (arr[i] % 2 != 0) { odd_element_cnt++; } } // Store number of replacements required var moves = Math.floor((odd_element_cnt)/2); // Two extra moves will be required // to make the last odd element even if (odd_element_cnt % 2 != 0) moves += 2; // Print the minimum replacements document.write(moves);}// Driver Code var arr = [5, 6, 3, 7, 20]; N = arr.length; // Function call minMoves(arr, N);</script> |
Output:
3
Time complexity: O(N)
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!
… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/make-all-array-elements-even-by-replacing-any-pair-of-array-elements-with-their-sum/ […]