Given an array arr[] of size N, the task is to find the minimum increments by 1 required to be performed on the array elements such that the count of even and odd integers in the given array becomes equal. If it is not possible, then print “-1”.
Examples:
Input: arr[] = {1, 3, 4, 9}
Output: 1
Explanation:
Count of even and odd integers in the array are 1 and 3 respectively.
Increment arr[3] ( = 9) by 1 to make it 10(even).
So, as the count of even and odd integer are the same after the above steps. Hence, the minimum increment operations is 1.Input: arr[] = {2, 2, 2, 2}
Output: 2
Approach: The idea to solve the given problem is as follows:
- If N is even, then traverse the array and keep a count of odd and even integers. The absolute difference of the count of even and odd integers divided by 2 gives the minimum increment operations required to make even and odd numbers equal.
- If N is odd, then it is not possible to make even and odd numbers equal, hence print “-1”.
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 min operations// to make even and odd count equalint minimumIncrement(int arr[], int N){ // Odd size will never make odd // and even counts equal if (N % 2 != 0) { cout << "-1"; exit(0); } // Stores the count of even // numbers in the array arr[] int cntEven = 0; // Stores count of odd numbers // in the array arr[] int cntOdd = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If arr[i] is an // even number if (arr[i] % 2 == 0) { // Update cntEven cntEven += 1; } } // Odd numbers in arr[] cntOdd = N - cntEven; // Return absolute difference // divided by 2 return abs(cntEven - cntOdd) / 2;}// Driver Codeint main(){ int arr[] = { 1, 3, 4, 9 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << minimumIncrement(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*; import java.lang.*;class GFG{ // Function to find min operations// to make even and odd count equalstatic int minimumIncrement(int arr[], int N){ // Odd size will never make odd // and even counts equal if (N % 2 != 0) { System.out.println( "-1"); System.exit(0); } // Stores the count of even // numbers in the array arr[] int cntEven = 0; // Stores count of odd numbers // in the array arr[] int cntOdd = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If arr[i] is an // even number if (arr[i] % 2 == 0) { // Update cntEven cntEven += 1; } } // Odd numbers in arr[] cntOdd = N - cntEven; // Return absolute difference // divided by 2 return Math.abs(cntEven - cntOdd) / 2;} // Driver code public static void main(String[] args) { int arr[] = { 1, 3, 4, 9 }; int N = arr.length; // Function call System.out.println(minimumIncrement(arr, N));} } // This code is contributed by code_hunt. |
Python3
# Python3 program for the above approach# Function to find min operations# to make even and odd count equaldef minimumIncrement(arr, N): # Odd size will never make odd # and even counts equal if (N % 2 != 0): print("-1") return # Stores the count of even # numbers in the array arr[] cntEven = 0 # Stores count of odd numbers # in the array arr[] cntOdd = 0 # Traverse the array arr[] for i in range(N): # If arr[i] is an # even number if (arr[i] % 2 == 0): # Update cntEven cntEven += 1 # Odd numbers in arr[] cntOdd = N - cntEven # Return absolute difference # divided by 2 return abs(cntEven - cntOdd) // 2# Driver Codeif __name__ == '__main__': arr = [1, 3, 4, 9] N = len(arr) # Function call print (minimumIncrement(arr, N)) # This code is contributed by mohit kumar 29. |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to find min operations// to make even and odd count equalstatic int minimumIncrement(int[] arr, int N){ // Odd size will never make odd // and even counts equal if (N % 2 != 0) { Console.WriteLine( "-1"); Environment.Exit(0); } // Stores the count of even // numbers in the array arr[] int cntEven = 0; // Stores count of odd numbers // in the array arr[] int cntOdd = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If arr[i] is an // even number if (arr[i] % 2 == 0) { // Update cntEven cntEven += 1; } } // Odd numbers in arr[] cntOdd = N - cntEven; // Return absolute difference // divided by 2 return Math.Abs(cntEven - cntOdd) / 2;} // Driver Code public static void Main() { int[] arr = { 1, 3, 4, 9 }; int N = arr.Length; // Function call Console.WriteLine(minimumIncrement(arr, N)); }}// This code is contributed by susmitakundugoaldanga. |
Javascript
<script>// Javascript program for the above approach // Function to find min operations // to make even and odd count equal function minimumIncrement(arr , N) { // Odd size will never make odd // and even counts equal if (N % 2 != 0) { document.write("-1"); System.exit(0); } // Stores the count of even // numbers in the array arr var cntEven = 0; // Stores count of odd numbers // in the array arr var cntOdd = 0; // Traverse the array arr for (i = 0; i < N; i++) { // If arr[i] is an // even number if (arr[i] % 2 == 0) { // Update cntEven cntEven += 1; } } // Odd numbers in arr cntOdd = N - cntEven; // Return absolute difference // divided by 2 return Math.abs(cntEven - cntOdd) / 2; } // Driver code var arr = [ 1, 3, 4, 9 ]; var N = arr.length; // Function call document.write(minimumIncrement(arr, N));// This code contributed by umadevi9616</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!
