Operación mínima para hacer que todos los elementos sean iguales en la array

Dada una array con n enteros positivos. Necesitamos encontrar el número mínimo de operaciones para hacer que todos los elementos sean iguales. Podemos realizar sumas, multiplicaciones, restas o divisiones con cualquier elemento de un elemento de array. 

Ejemplos: 

Input : arr[] = {1, 2, 3, 4}
Output : 3
Since all elements are different, 
we need to perform at least three
operations to make them same. For
example, we can make them all 1
by doing three subtractions. Or make
them all 3 by doing three additions.

Input : arr[] = {1, 1, 1, 1}
Output : 0

Para hacer que todos los elementos sean iguales, puede seleccionar un valor objetivo y luego puede hacer que todos los elementos sean iguales a eso. Ahora, para convertir un solo elemento en valor objetivo, puede realizar una sola operación solo una vez. De esta manera, puede lograr su tarea en un máximo de n operaciones, pero debe minimizar este número de operaciones y, para esto, su selección de objetivo es muy importante porque si selecciona un objetivo cuya frecuencia en la array es x, entonces debe realizar solo nx más operaciones ya que ya tiene x elementos iguales a su valor objetivo. Así que finalmente, nuestra tarea se reduce a encontrar el elemento con la máxima frecuencia. Esto se puede lograr por diferentes medios, como el método iterativo en O (n ^ 2), la clasificación en O (nlogn) y el hash en la complejidad del tiempo O (n). 

Implementación:

// CPP program to find the minimum number of
// operations required to make all elements
// of array equal
#include <bits/stdc++.h>
using namespace std;
 
// function for min operation
int minOperation (int arr[], int n)
{
    // Insert all elements in hash.
    unordered_map<int, int> hash;
    for (int i=0; i<n; i++)
        hash[arr[i]]++;
 
    // find the max frequency
    int max_count = 0;
    for (auto i : hash)
        if (max_count < i.second)
            max_count = i.second;
 
    // return result
    return (n - max_count);
}
 
// driver program
int main()
{
    int arr[] = {1, 5, 2, 1, 3, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minOperation(arr, n);
    return 0;
}

// JAVA Code For Minimum operation to make
// all elements equal in array
import java.util.*;
 
class GFG {
     
    // function for min operation
    public static int minOperation (int arr[], int n)
    {
        // Insert all elements in hash.
       HashMap<Integer, Integer> hash = new HashMap<Integer,
                                           Integer>();
         
        for (int i=0; i<n; i++)
            if(hash.containsKey(arr[i]))
                hash.put(arr[i], hash.get(arr[i])+1);
            else hash.put(arr[i], 1);
         
        // find the max frequency
        int max_count = 0;
        Set<Integer> s = hash.keySet();
         
        for (int i : s)
            if (max_count < hash.get(i))
                max_count = hash.get(i);
      
        // return result
        return (n - max_count);
    }
     
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int arr[] = {1, 5, 2, 1, 3, 2, 1};
        int n = arr.length;
        System.out.print(minOperation(arr, n));
             
    }
}
   
// This code is contributed by Arnav Kr. Mandal.

# Python3 program to find the minimum
# number of operations required to
# make all elements of array equal
from collections import defaultdict
 
# Function for min operation
def minOperation(arr, n):
 
    # Insert all elements in hash.
    Hash = defaultdict(lambda:0)
    for i in range(0, n):
        Hash[arr[i]] += 1
 
    # find the max frequency
    max_count = 0
    for i in Hash:
        if max_count < Hash[i]:
            max_count = Hash[i]
 
    # return result
    return n - max_count
 
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 5, 2, 1, 3, 2, 1]
    n = len(arr)
    print(minOperation(arr, n))
     
# This code is contributed
# by Rituraj Jain

// C# Code For Minimum operation to make
// all elements equal in array
using System;
using System.Collections.Generic;
     
class GFG
{
     
    // function for min operation
    public static int minOperation (int []arr, int n)
    {
        // Insert all elements in hash.
        Dictionary<int,int> m = new Dictionary<int,int>();
        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);
            }
        }
         
        // find the max frequency
        int max_count = 0;
        HashSet<int> s = new HashSet<int>(m.Keys);
         
        foreach (int i in s)
            if (max_count < m[i])
                max_count = m[i];
     
        // return result
        return (n - max_count);
    }
     
    /* Driver code */
    public static void Main(String[] args)
    {
        int []arr = {1, 5, 2, 1, 3, 2, 1};
        int n = arr.Length;
        Console.Write(minOperation(arr, n));
             
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript Code For Minimum operation to make
// all elements equal in array
 
// function for min operation
function minOperation(arr, n) {
    // Insert all elements in hash.
    let hash = new Map();
 
    for (let i = 0; i < n; i++)
        if (hash.has(arr[i]))
            hash.set(arr[i], hash.get(arr[i]) + 1);
        else hash.set(arr[i], 1);
 
    // find the max frequency
    let max_count = 0;
    let s = hash.keys();
 
    for (let i of s)
        if (max_count < hash.get(i))
            max_count = hash.get(i);
 
    // return result
    return (n - max_count);
}
 
/* Driver program to test above function */
 
let arr = [1, 5, 2, 1, 3, 2, 1];
let n = arr.length;
document.write(minOperation(arr, n));
 
 
// This code is contributed by _saurabh_jaiswal
 
</script>

4

Complejidad temporal: O(n)
Espacio auxiliar: O(n)

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.