Encuentre el número mínimo de operaciones requeridas para hacer que todos los elementos de la array sean iguales

Dada una array arr[] de tamaño N . La tarea es hacer que todos los elementos de la array sean iguales aplicando las siguientes operaciones un número mínimo de veces: 
 

1. Elija un par de índices (i, j) tales que |i – j| = 1 (los índices i y j son adyacentes) y establecer arr[i] = arr[i] + |arr[i] – arr[j]|
2. Elija un par de índices (i, j) tales que |i – j| = 1 (los índices i y j son adyacentes) y establecer arr[i] = arr[i] – |arr[i] – arr[j]|

Ejemplos: 
 

Entrada: arr[] = { 2, 4, 6 } 
Salida: 2 
Aplicar el segundo tipo de operación en la array dada da {2, 2, 6}. 
Ahora, aplicar el segundo tipo de operación nuevamente en la array modificada da {2, 2, 2}. 
Entrada: arr[] = { 1, 1, 1} 
Salida: 0 
Todos los elementos de la array ya son iguales. 
 

Enfoque: busquemos el elemento más frecuente en la array (usando el mapa para almacenar las frecuencias de todos los elementos). Sea este elemento x . Si observamos las operaciones más detenidamente, podemos ver que la parte de estas operaciones significa fijar el elemento p al elemento q . Si p < q , entonces se debe realizar la primera operación, de lo contrario, la segunda.
Ahora, considere el número de operaciones en la respuesta óptima. Es obvio que necesitamos al menos n – freq(x) operaciones para igualar todos los elementos. Y también es obvio que siempre podemos hacerlo con n – freq(x) tales operaciones, que es el número mínimo de operaciones requeridas.
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 operations
// required to make all array elements equal
int minOperations(int arr[], int n)
{
 
    // To store the frequency
    // of all the array elements
    unordered_map<int, int> mp;
 
    // Traverse through array elements and
    // update frequencies
    for (int i = 0; i < n; i++)
        mp[arr[i]]++;
 
    // To store the maximum frequency
    // of an element from the array
    int maxFreq = INT_MIN;
 
    // Traverse through the map and find
    // the maximum frequency for any element
    for (auto x : mp)
        maxFreq = max(maxFreq, x.second);
 
    // Return the minimum operations required
    return (n - maxFreq);
}
 
// Driver code
int main()
{
    int arr[] = { 2, 4, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << minOperations(arr, n);
 
    return 0;
}

// Java implementation of the above approach
import java.util.*;
 
class GFG
{
 
    // Function to return the minimum operations
    // required to make all array elements equal
    static int minOperations(int arr[], int n)
    {
 
        // To store the frequency
        // of all the array elements
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
 
        // Traverse through array elements and
        // update frequencies
        for (int i = 0; i < n; i++)
        {
            if (mp.containsKey(arr[i]))
            {
                mp.put(arr[i], mp.get(arr[i]) + 1);
            }
            else
            {
                mp.put(arr[i], 1);
            }
        }
 
        // To store the maximum frequency
        // of an element from the array
        int maxFreq = Integer.MIN_VALUE;
 
        // Traverse through the map and find
        // the maximum frequency for any element
        maxFreq = Collections.max(mp.entrySet(),
                Comparator.comparingInt(Map.Entry::getKey)).getValue();
                 
        // Return the minimum operations required
        return (n - maxFreq);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = {2, 4, 6};
        int n = arr.length;
        System.out.println(minOperations(arr, n));
    }
}
 
/* This code contributed by PrinciRaj1992 */

# Python3 implementation of the approach
import sys
 
# Function to return the minimum operations
# required to make all array elements equal
def minOperations(arr, n) :
 
    # To store the frequency
    # of all the array elements
    mp = dict.fromkeys(arr, 0);
 
    # Traverse through array elements and
    # update frequencies
    for i in range(n) :
        mp[arr[i]] += 1;
 
    # To store the maximum frequency
    # of an element from the array
    maxFreq = -(sys.maxsize - 1);
 
    # Traverse through the map and find
    # the maximum frequency for any element
    for key in mp :
        maxFreq = max(maxFreq, mp[key]);
 
    # Return the minimum operations required
    return (n - maxFreq);
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 2, 4, 6 ];
    n = len(arr) ;
 
    print(minOperations(arr, n));
 
# This code is contributed by Ryuga

// C# implementation of the above approach
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to return the minimum operations
    // required to make all array elements equal
    static int minOperations(int []arr, int n)
    {
 
        // To store the frequency
        // of all the array elements
        Dictionary<int,int> m = new Dictionary<int,int>();
 
        // Traverse through array elements and
        // update frequencies
        for (int i = 0; i < n; i++)
        {
            if(m.ContainsKey(arr[i]))
            {
                var val = m[arr[i]];
                m.Remove(arr[i]);
                m.Add(arr[i], val + 1);
            }
            else
            {
                m.Add(arr[i], 1);
            }    
        }
 
        // To store the maximum frequency
        // of an element from the array
        int maxFreq = int.MinValue;
 
        // Traverse through the map and find
        // the maximum frequency for any element
        maxFreq = m.Values.Max();
                 
        // Return the minimum operations required
        return (n - maxFreq);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int []arr = {2, 4, 6};
        int n = arr.Length;
        Console.WriteLine(minOperations(arr, n));
    }
}
 
// This code contributed by Rajput-Ji

<script>
 
// JavaScript implementation of the approach
 
// Function to return the minimum operations
// required to make all array elements equal
function minOperations(arr, n) {
 
    // To store the frequency
    // of all the array elements
    let mp = new Map();
 
    // Traverse through array elements and
    // update frequencies
    for (let i = 0; i < n; i++) {
        if (mp.has(arr[i])) {
            mp.set(arr[i], mp.get(arr[i]) + 1)
        } else {
            mp.set(arr[i], 1)
        }
    }
 
    // To store the maximum frequency
    // of an element from the array
    let maxFreq = Number.MIN_SAFE_INTEGER;
 
    // Traverse through the map and find
    // the maximum frequency for any element
    for (let x of mp)
        maxFreq = Math.max(maxFreq, x[1]);
 
    // Return the minimum operations required
    return (n - maxFreq);
}
 
// Driver code
 
let arr = [2, 4, 6];
let n = arr.length;
 
document.write(minOperations(arr, n));
 
 
// This code is contributed by _saurabh_jaiswal
 
</script>

2

Complejidad de tiempo: O(N), donde N representa el tamaño de la array dada.

Espacio auxiliar: O(N), donde N representa el tamaño de la array dada.