Minimum increments required to make array elements alternately even and odd

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 ncrement 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:

Python3

def minIncr(arr):                  forEven = 0             for i in range(len(arr)):                                       if i % 2:             if not arr[i] % 2:                 forEven += 1                                       else:             if arr[i] % 2:                 forEven += 1             return min(forEven, len(arr)-forEven)       arr = [1, 4, 6, 8, 9, 5] print(minIncr(arr))

Time Complexity: O(N)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)