Given an array arr[] consisting of N positive integers, the task is to find the minimum number of increments required to make the array arr[] alternating sequence of even and odd numbers.
Examples:
Input: arr[] = {1, 4, 6, 8, 9, 5}
Output: 2
Explanation:
Incrementing arr[2] modifies arr[] to {1, 4, 7, 8, 9, 5}.
Incrementing arr[5] by 1 modifies arr[] to {1, 4, 7, 8, 9, 6}.Input: arr[] = {3, 5, 7, 9, 4, 2}
Output: 3
Explanation:
Incrementing arr[0] by 1 modifies arr[] to {4, 5, 7, 9, 4, 2}.
Incrementing arr[2] by 1 modifies arr[] to {4, 5, 8, 9, 4, 2}.
Incrementing arr[5] by 1 modifies arr[] to {4, 5, 8, 9, 4, 3}.
Approach: To solve the given problem, the idea is to check the number of increments required for making the array elements odd and even alternately as well as even and odd alternately. Finally, print the minimum of the two counts of increments obtained. Follow the steps below to solve the problem:
- Initialize a variable, say cnt as 0, to store the count of increments required to convert the array into an alternating sequence of even and odd numbers or vice-versa.
- Traverse the array arr[] using the variable i and perform the following steps:
- If i is even and arr[i] is odd, then increment cnt by 1.
- If i is odd and arr[i] is even, then increment cnt by 1.
- After completing the above steps, the minimum of cnt and (N – cnt) is the required result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to find the minimum number of// increments required to make the array// even-odd alternately or vice-versaint minIncr(int *arr,int n){ // Store the minimum number of // increments required int forEven = 0; // Traverse the array arr[] for(int i = 0; i < n; i++) { // Increment forEven if even // element is present at an // odd index if(i % 2){ if((arr[i] % 2) == 0) forEven += 1; } // Increment forEven if odd // element is present at an // even index else{ if(arr[i] % 2) forEven += 1; } } // Return the minimum number of increments return min(forEven, n - forEven);}int main(){ // Driver Code int arr[] = {1, 4, 6, 8, 9, 5}; int n = sizeof(arr)/sizeof(arr[0]); cout<<minIncr(arr,n); return 0;}// This code is contributed by rohitsingh07052. |
Java
// Java program for the above approachclass GFG{ // Function to find the minimum number of// increments required to make the array// even-odd alternately or vice-versastatic int minIncr(int []arr, int n){ // Store the minimum number of // increments required int forEven = 0; // Traverse the array arr[] for(int i = 0; i < n; i++) { // Increment forEven if even // element is present at an // odd index if (i % 2 == 1) { if ((arr[i] % 2) == 0) forEven += 1; } // Increment forEven if odd // element is present at an // even index else { if (arr[i] % 2 == 1) forEven += 1; } } // Return the minimum number of increments return Math.min(forEven, n - forEven);}// Driver Codepublic static void main (String[] args){ int arr[] = { 1, 4, 6, 8, 9, 5 }; int n = arr.length; System.out.println(minIncr(arr,n));}}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to find the minimum number of# increments required to make the array# even-odd alternately or vice-versadef minIncr(arr): # Store the minimum number of # increments required forEven = 0 # Traverse the array arr[] for i in range(len(arr)): # Increment forEven if even # element is present at an # odd index if i % 2: if not arr[i] % 2: forEven += 1 # Increment forEven if odd # element is present at an # even index else: if arr[i] % 2: forEven += 1 # Return the minimum number of increments return min(forEven, len(arr)-forEven)# Driver Codearr = [1, 4, 6, 8, 9, 5]print(minIncr(arr)) |
C#
// C# program for the above approachusing System;public class GFG{ // Function to find the minimum number of // increments required to make the array // even-odd alternately or vice-versa static int minIncr(int []arr, int n) { // Store the minimum number of // increments required int forEven = 0; // Traverse the array []arr for(int i = 0; i < n; i++) { // Increment forEven if even // element is present at an // odd index if (i % 2 == 1) { if ((arr[i] % 2) == 0) forEven += 1; } // Increment forEven if odd // element is present at an // even index else { if (arr[i] % 2 == 1) forEven += 1; } } // Return the minimum number of increments return Math.Min(forEven, n - forEven); } // Driver Code public static void Main(String[] args) { int []arr = { 1, 4, 6, 8, 9, 5 }; int n = arr.Length; Console.WriteLine(minIncr(arr,n)); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approach// Function to find the minimum number of// increments required to make the array// even-odd alternately or vice-versafunction minIncr(arr, n){ // Store the minimum number of // increments required let forEven = 0; // Traverse the array arr[] for(let i = 0; i < n; i++) { // Increment forEven if even // element is present at an // odd index if(i % 2){ if((arr[i] % 2) == 0) forEven += 1; } // Increment forEven if odd // element is present at an // even index else{ if(arr[i] % 2) forEven += 1; } } // Return the minimum number of increments return Math.min(forEven, n - forEven);}// Driver Codelet arr = [1, 4, 6, 8, 9, 5];let n = arr.length;document.write(minIncr(arr,n));</script> |
Output:
2
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!
