Dada una array arr[] de tamaño N , la tarea es encontrar los incrementos mínimos en 1 necesarios para realizar en los elementos de la array de modo que el recuento de enteros pares e impares en la array dada sea igual. Si no es posible, imprima “-1” .
Ejemplos:
Entrada: arr[] = {1, 3, 4, 9}
Salida: 1
Explicación:
La cantidad de enteros pares e impares en la array es 1 y 3 respectivamente.
Incremente arr[3] ( = 9) en 1 para convertirlo en 10 (par).
Entonces, como el conteo de enteros pares e impares es el mismo después de los pasos anteriores. Por lo tanto, las operaciones de incremento mínimo es 1.Entrada: arr[] = {2, 2, 2, 2}
Salida: 2
Planteamiento: La idea para resolver el problema dado es la siguiente:
- Si N es par , entonces recorra la array y mantenga un conteo de enteros pares e impares . La diferencia absoluta de la cuenta de enteros pares e impares dividida por 2 da las operaciones de incremento mínimas requeridas para hacer que los números pares e impares sean iguales.
- Si N es impar , entonces no es posible hacer que los números pares e impares sean iguales, por lo tanto, imprima «-1» .
A continuación se muestra la implementación del enfoque anterior:
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 equal
int 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 Code
int 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 approach
import java.util.*;
import java.lang.*;
class GFG
{
// Function to find min operations
// to make even and odd count equal
static 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 equal
def 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 Code
if __name__ == '__main__':
arr = [1, 3, 4, 9]
N = len(arr)
# Function call
print (minimumIncrement(arr, N))
# Thiss code is contributed by mohit kumar 29.
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find min operations
// to make even and odd count equal
static 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>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sohailahmed46khan786 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA