Given an array arr[] of size N, the task is to make all array elements even by replacing a pair of adjacent elements with their sum.
Examples:
Input: arr[] = { 2, 4, 5, 11, 6 }
Output: 1
Explanation:
Replacing a pair (arr[2], arr[3]) with their sum ( = 5 + 11 = 16) modifies arr[] to { 2, 4, 16, 16, 6 }
Since all array elements are even, the required output is 1.Input: arr[] = { 1, 2, 4, 3, 11 }
Output: 3
Explanation:
Replacing the pair (arr[3], arr[4]) and replacing them with their sum ( = 3 + 11 = 14) modifies arr[] to { 1, 2, 4, 14, 14 }
Replacing the pair (arr[0], arr[1]) and replacing them with their sum ( = 1 + 2 = 3) modifies arr[] to { 3, 3, 4, 14, 14 }
Replacing the pair (arr[0], arr[1]) with their sum ( = 3 + 3 = 6) modifies arr[] to { 6, 6, 4, 14, 14 }.
Therefore, the required output is 3.
Approach: The idea is to use the fact that the sum of two odd numbers generates an even number. Follow the steps below to solve the problem:
- Initialize two integers, say res, to count the number of replacements, and odd_continuous_segment, to count the number of continuous odd numbers
- Traverse the array and check the following conditions for every array element:
- If arr[i] is odd, then increment the count of odd_continuous_segment by 1
- Otherwise, if odd_continuous_segment is odd, then increment res by odd_continuous_segment/2. Otherwise, increment res by odd_continuous_segment / 2 + 2 and assign odd_continuous_segment to 0.
- Check if odd_continuous_segment is odd. If found to be true, then increment res by odd_continuous_segment / 2. Otherwise increment res by (odd_continuous_segment / 2 + 2)
- Finally, print the obtained value of res
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <iostream>using namespace std;// Function to find minimum count of operations// required to make all array elements evenint make_array_element_even(int arr[], int N){ // Stores minimum count of replacements // to make all array elements even int res = 0; // Stores the count of odd // continuous numbers int odd_cont_seg = 0; // Traverse the array for (int i = 0; i < N; i++) { // If arr[i] is an odd number if (arr[i] % 2 == 1) { // Update odd_cont_seg odd_cont_seg++; } else { if (odd_cont_seg > 0) { // If odd_cont_seg is even if (odd_cont_seg % 2 == 0) { // Update res res += odd_cont_seg / 2; } else { // Update res res += (odd_cont_seg / 2) + 2; } // Reset odd_cont_seg = 0 odd_cont_seg = 0; } } } // If odd_cont_seg exceeds 0 if (odd_cont_seg > 0) { // If odd_cont_seg is even if (odd_cont_seg % 2 == 0) { // Update res res += odd_cont_seg / 2; } else { // Update res res += odd_cont_seg / 2 + 2; } } // Print the result return res;}// Drivers Codeint main(){ int arr[] = { 2, 4, 5, 11, 6 }; int N = sizeof(arr) / sizeof(arr[0]); cout << make_array_element_even(arr, N); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ // Function to find minimum count of operations // required to make all array elements even static int make_array_element_even(int arr[], int N) { // Stores minimum count of replacements // to make all array elements even int res = 0; // Stores the count of odd // continuous numbers int odd_cont_seg = 0; // Traverse the array for (int i = 0; i < N; i++) { // If arr[i] is an odd number if (arr[i] % 2 == 1) { // Update odd_cont_seg odd_cont_seg++; } else { if (odd_cont_seg > 0) { // If odd_cont_seg is even if (odd_cont_seg % 2 == 0) { // Update res res += odd_cont_seg / 2; } else { // Update res res += (odd_cont_seg / 2) + 2; } // Reset odd_cont_seg = 0 odd_cont_seg = 0; } } } // If odd_cont_seg exceeds 0 if (odd_cont_seg > 0) { // If odd_cont_seg is even if (odd_cont_seg % 2 == 0) { // Update res res += odd_cont_seg / 2; } else { // Update res res += odd_cont_seg / 2 + 2; } } // Print the result return res; } // Drivers Code public static void main(String[] args) { int arr[] = { 2, 4, 5, 11, 6 }; int N = arr.length; System.out.print(make_array_element_even(arr, N)); }}// This code is contributed by shikhasingrajput |
Python3
# Python program to implement# the above approach# Function to find minimum count of operations# required to make all array elements evendef make_array_element_even(arr, N): # Stores minimum count of replacements # to make all array elements even res = 0 # Stores the count of odd # continuous numbers odd_cont_seg = 0 # Traverse the array for i in range(0, N): # If arr[i] is an odd number if (arr[i] % 2 == 1): # Update odd_cont_seg odd_cont_seg+=1 else: if (odd_cont_seg > 0): # If odd_cont_seg is even if (odd_cont_seg % 2 == 0): # Update res res += odd_cont_seg // 2 else: # Update res res += (odd_cont_seg // 2) + 2 # Reset odd_cont_seg = 0 odd_cont_seg = 0 # If odd_cont_seg exceeds 0 if (odd_cont_seg > 0): # If odd_cont_seg is even if (odd_cont_seg % 2 == 0): # Update res res += odd_cont_seg // 2 else: # Update res res += odd_cont_seg // 2 + 2 # Print the result return res# Drivers Codearr = [2, 4, 5, 11, 6]N = len(arr)print(make_array_element_even(arr, N))# This code is contributed by shubhamsingh10 |
C#
// C# program to implement// the above approachusing System;public class GFG{ // Function to find minimum count of operations // required to make all array elements even static int make_array_element_even(int []arr, int N) { // Stores minimum count of replacements // to make all array elements even int res = 0; // Stores the count of odd // continuous numbers int odd_cont_seg = 0; // Traverse the array for (int i = 0; i < N; i++) { // If arr[i] is an odd number if (arr[i] % 2 == 1) { // Update odd_cont_seg odd_cont_seg++; } else { if (odd_cont_seg > 0) { // If odd_cont_seg is even if (odd_cont_seg % 2 == 0) { // Update res res += odd_cont_seg / 2; } else { // Update res res += (odd_cont_seg / 2) + 2; } // Reset odd_cont_seg = 0 odd_cont_seg = 0; } } } // If odd_cont_seg exceeds 0 if (odd_cont_seg > 0) { // If odd_cont_seg is even if (odd_cont_seg % 2 == 0) { // Update res res += odd_cont_seg / 2; } else { // Update res res += odd_cont_seg / 2 + 2; } } // Print the result return res; } // Drivers Code public static void Main(String[] args) { int []arr = { 2, 4, 5, 11, 6 }; int N = arr.Length; Console.Write(make_array_element_even(arr, N)); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to implement// the above approach// Function to find minimum count of operations// required to make all array elements evenfunction make_array_element_even(arr, N){ // Stores minimum count of replacements // to make all array elements even let res = 0; // Stores the count of odd // continuous numbers let odd_cont_seg = 0; // Traverse the array for(let i = 0; i < N; i++) { // If arr[i] is an odd number if (arr[i] % 2 == 1) { // Update odd_cont_seg odd_cont_seg++; } else { if (odd_cont_seg > 0) { // If odd_cont_seg is even if (odd_cont_seg % 2 == 0) { // Update res res += odd_cont_seg / 2; } else { // Update res res += (odd_cont_seg / 2) + 2; } // Reset odd_cont_seg = 0 odd_cont_seg = 0; } } } // If odd_cont_seg exceeds 0 if (odd_cont_seg > 0) { // If odd_cont_seg is even if (odd_cont_seg % 2 == 0) { // Update res res += odd_cont_seg / 2; } else { // Update res res += odd_cont_seg / 2 + 2; } } // Print the result return res;}// Driver Code// Given array arr[]let arr = [ 2, 4, 5, 11, 6 ];let N = arr.length;document.write(make_array_element_even(arr, N));// This code is contributed by splevel62</script> |
Output:
1
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!
