Costo mínimo para hacer que todos los elementos de la array sean iguales – Part 1

Dada una array arr[] que consta de N enteros positivos, la tarea es hacer que todos los valores de esta array sean iguales a algún valor entero con un costo mínimo después de realizar las siguientes operaciones cualquier cantidad de veces (posiblemente cero). 
 

1. Reduzca el elemento de array en 2 o increméntelo en 2 con costo cero.
2. Reduzca el elemento de la array en 1 o auméntelo en 1 con un costo unitario.

Ejemplos: 
 

Entrada: arr[] = {2, 4, 3, 1, 5} 
Salida: 2 
Podemos cambiar el tercer elemento a 5 incurriendo en 0 costo. 
Podemos cambiar el 4to elemento a 5 (1 -> 3 -> 5) incurriendo en 0 costo. 
Ahora la array es, 2 4 5 5 5
Podemos cambiar el primer elemento a 5 (2 -> 4 -> 5) incurriendo en un costo unitario. 
Podemos cambiar el segundo elemento a 5 incurriendo en costo unitario. 
La array final es, 5 5 5 5 5 
Costo total = 1 + 1 = 2
Entrada: arr[] = {2, 2, 2, 3} 
Salida: 1 
Podemos disminuir el último elemento en 1 incurriendo en el costo unitario solamente. 
 

Enfoque: La idea básica es contar el número de elementos pares e impares presentes en la array e imprimir el mínimo de estos dos como respuesta. Este enfoque funciona porque podemos hacer que todos los elementos pares sean iguales y todos los elementos impares iguales sin incurrir en ningún costo (Operación 1). La array actualizada después de realizar estas operaciones solo contendrá los elementos x y x + 1, donde uno es impar y el otro es par. Los elementos de ambos tipos se pueden cambiar al otro tipo con 1 costo unitario y para minimizar el costo, el resultado será el mínimo (frecuencia (x), frecuencia (x + 1)).
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum cost
// to make each array element equal
int minCost(int arr[], int n)
{
    // To store the count of even numbers
    // present in the array
    int count_even = 0;
 
    // To store the count of odd numbers
    // present in the array
    int count_odd = 0;
 
    // Iterate through the array and
    // find the count of even numbers
    // and odd numbers
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 == 0)
            count_even++;
        else
            count_odd++;
    }
 
    return min(count_even, count_odd);
}
 
// Driver code
int main()
{
    int arr[] = { 2, 4, 3, 1, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << minCost(arr, n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
// Function to return the minimum cost
// to make each array element equal
static int minCost(int arr[], int n)
{
    // To store the count of even numbers
    // present in the array
    int count_even = 0;
 
    // To store the count of odd numbers
    // present in the array
    int count_odd = 0;
 
    // Iterate through the array and
    // find the count of even numbers
    // and odd numbers
    for (int i = 0; i < n; i++)
    {
        if (arr[i] % 2 == 0)
            count_even++;
        else
            count_odd++;
    }
 
    return Math.min(count_even, count_odd);
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 2, 4, 3, 1, 5 };
    int n = arr.length;
 
    System.out.println(minCost(arr, n));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation of the approach
 
# Function to return the minimum cost
# to make each array element equal
def minCost(arr, n):
     
    # To store the count of even numbers
    # present in the array
    count_even = 0
 
    # To store the count of odd numbers
    # present in the array
    count_odd = 0
 
    # Iterate through the array and
    # find the count of even numbers
    # and odd numbers
    for i in range(n):
        if (arr[i] % 2 == 0):
            count_even += 1
        else:
            count_odd += 1
 
    return min(count_even, count_odd)
 
# Driver code
arr = [2, 4, 3, 1, 5]
n = len(arr)
 
print(minCost(arr, n))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
     
class GFG
{
     
// Function to return the minimum cost
// to make each array element equal
static int minCost(int []arr, int n)
{
    // To store the count of even numbers
    // present in the array
    int count_even = 0;
 
    // To store the count of odd numbers
    // present in the array
    int count_odd = 0;
 
    // Iterate through the array and
    // find the count of even numbers
    // and odd numbers
    for (int i = 0; i < n; i++)
    {
        if (arr[i] % 2 == 0)
            count_even++;
        else
            count_odd++;
    }
 
    return Math.Min(count_even, count_odd);
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 2, 4, 3, 1, 5 };
    int n = arr.Length;
 
    Console.WriteLine(minCost(arr, n));
}
}
     
// This code is contributed by Princi Singh

<script>
// javascript implementation of the approach   
// Function to return the minimum cost
    // to make each array element equal
    function minCost(arr, n)
    {
     
        // To store the count of even numbers
        // present in the array
        var count_even = 0;
 
        // To store the count of odd numbers
        // present in the array
        var count_odd = 0;
 
        // Iterate through the array and
        // find the count of even numbers
        // and odd numbers
        for (i = 0; i < n; i++)
        {
            if (arr[i] % 2 == 0)
                count_even++;
            else
                count_odd++;
        }
        return Math.min(count_even, count_odd);
    }
 
    // Driver code
        var arr = [ 2, 4, 3, 1, 5 ];
        var n = arr.length;
        document.write(minCost(arr, n));
 
// This code is contributed by Rajput-Ji.
</script>

2

Complejidad de tiempo: O(N) 
Complejidad de espacio: O(1)