Cuente los decrementos al elemento más pequeño más cercano requerido para hacer que todos los elementos de la array sean iguales

Dada una array arr[] que consta de N enteros no negativos, la tarea es encontrar el número de operaciones necesarias para que todos los elementos de la array sean iguales. En cada operación, cualquier elemento de array se puede cambiar a su elemento de array más pequeño más cercano.

Ejemplos:

Entrada: arr[] = {2, 5, 4, 3, 5, 4}
Salida: 11
Explicación: 
Paso 1: Reemplace todos los 5 con 4. Por lo tanto, arr[] = {2, 4, 4, 3, 4, 4}. Conteo de operaciones = 2
Paso 2: Reemplace todos los 4 con 3. Por lo tanto, arr[] = {2, 3, 3, 3, 3, 3}. Conteo de operaciones = 4
Pasos 3: Reemplace todos los 3 con 2. Por lo tanto, arr[] = {2, 2, 2, 2, 2, 2}. Número de operaciones = 5
Por lo tanto, número total de operaciones = 11

Entrada: arr[] = {2, 2, 2}
Salida: 0

Enfoque: La idea es utilizar un algoritmo de clasificación y una estructura de datos Map . Siga los pasos a continuación para resolver el problema:

1. Inicialice un mapa para almacenar la frecuencia de cada elemento del arreglo excepto el elemento mínimo donde las claves (K) son el conjunto de elementos únicos y los valores (V) son sus frecuencias.
2. Ordene el mapa en orden decreciente según las claves.
3. Inicialice dos variables ans y prev_val con 0 para almacenar la respuesta actual y el prefijo sum respectivamente.
4. Ahora itere el Mapa y agregue las frecuencias correspondientes de cada elemento junto con prev_val a ans como ans = ans + (freq) + prev_val
5. Mientras itera el Mapa , incremente prev_val cada vez por la frecuencia del elemento actual.
6. Después de recorrer el Mapa por completo, imprima ans como el número mínimo de operaciones.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the minimum number of
// decrements to make all elements equals
int MinimumNoOfOperations(int arr[], int n)
{
 
    // Find minimum element
    int min_ele = INT_MAX;
    for (int i = 0; i < n; ++i) {
        min_ele = min(min_ele, arr[i]);
    }
 
    // Stores frequencies of array elements
    map<int, int, greater<int> > mp;
 
    // Update frequencies in the Map
    for (int i = 0; i < n; ++i) {
 
        if (arr[i] == min_ele)
            continue;
        else
            mp[arr[i]]++;
    }
 
    // Iterate the map
    map<int, int>::iterator it;
 
    // Stores the count of
    // decrements at each iteration
    int prev_val = 0;
 
    // Stores the total
    // count of decrements
    int ans = 0;
 
    // Calculate the number of decrements
    for (it = mp.begin(); it != mp.end();
         ++it) {
 
        ans += (it->second + prev_val);
        prev_val += it->second;
    }
 
    // Return minimum operations
    return ans;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 2, 5, 4, 3, 5, 4 };
 
    // Given size
    int size = sizeof(arr)
               / sizeof(arr[0]);
 
    // Function call
    cout << MinimumNoOfOperations(
        arr, size);
    return 0;
}

// Java program for the
// above approach
import java.util.*;
 
class solution{
    
// Function to print the minimum
// number of decrements to make
// all elements equals
static int MinimumNoOfOperations(int arr[],
                                 int n)
{
  // Find minimum element
  int min_ele = Integer.MAX_VALUE;
   
  for (int i = 0; i < n; ++i)
  {
    min_ele = Math.min(min_ele,
                       arr[i]);
  }
 
  // Stores frequencies of array
  // elements
  TreeMap<Integer,
          Integer> mp =
          new TreeMap<Integer,
                      Integer>(
          Collections.reverseOrder());
 
  // Update frequencies in
  // the Map
  for (int i = 0; i < n; ++i)
  {
    if (arr[i] == min_ele)
      continue;
    else
      mp.put(arr[i],
      mp.getOrDefault(arr[i], 0) + 1);
  }
 
  // Stores the count of
  // decrements at each
  // iteration
  int prev_val = 0;
 
  // Stores the total
  // count of decrements
  int ans = 0;
 
  // Calculate the number of
  // decrements
  for (Map.Entry<Integer,
                 Integer> it : mp.entrySet())
  {
    ans += (it.getValue() + prev_val);
    prev_val += it.getValue();
  }
 
  // Return minimum operations
  return ans;
}
 
// Driver Code
public static void main(String args[])
{
  // Given array
  int arr[] = {2, 5, 4, 3, 5, 4};
   
  // Given size
  int size = arr.length;
   
  // Function call
  System.out.println(
  MinimumNoOfOperations(arr, size));
}
}
 
// This code is contributed by bgangwar59

# Python3 program for the above approach
import sys
 
# Function to print the minimum number of
# decrements to make all elements equals
def MinimumNoOfOperations(arr, n):
     
    # Find minimum element
    min_ele = sys.maxsize
     
    for i in range(n):
        min_ele = min(min_ele, arr[i])
 
    # Stores frequencies of array elements
    mp = {}
 
    # Update frequencies in the Map
    for i in range(n):
        if (arr[i] == min_ele):
            continue
        else:
            mp[arr[i]] = mp.get(arr[i], 0) + 1
             
    # Stores the count of
    # decrements at each iteration
    prev_val = 0
 
    # Stores the total
    # count of decrements
    ans = 0
 
    # Calculate the number of decrements
    for it in mp:
        ans += (mp[it] + prev_val)
        prev_val += mp[it]
 
    # Return minimum operations
    return ans
 
# Driver Code
if __name__ == '__main__':
     
    # Given array
    arr = [ 2, 5, 4, 3, 5, 4 ]
 
    # Given size
    size = len(arr)
 
    # Function call
    print(MinimumNoOfOperations(arr, size))
 
# This code is contributed by mohit kumar 29

// C# program for the
// above approach
using System.Collections.Generic;
using System;
using System.Linq;
 
class GFG{
    
// Function to print the minimum
// number of decrements to make
// all elements equals
static int MinimumNoOfOperations(int []arr,
                                 int n)
{
   
  // Find minimum element
  int min_ele = 1000000000;
   
  for(int i = 0; i < n; ++i)
  {
      min_ele = Math.Min(min_ele, arr[i]);
  }
 
  // Stores frequencies of array
  // elements
  Dictionary<int,
             int> mp = new Dictionary<int,
                                      int>();
 
  // Update frequencies in
  // the Map
  for(int i = 0; i < n; ++i)
  {
    if (arr[i] == min_ele)
      continue;
    else
    {
      if (mp.ContainsKey(arr[i]) == true)
        mp[arr[i]] += 1;
      else
        mp[arr[i]] = 1;   
    }
  }
 
  // Stores the count of
  // decrements at each
  // iteration
  int prev_val = 0;
 
  // Stores the total
  // count of decrements
  int ans = 0;
 
  // Calculate the number of
  // decrements
  var val = mp.Keys.ToList();
  foreach(var key in val)
  {
    ans += (mp[key] + prev_val);
    prev_val += mp[key];
  }
   
  // Return minimum operations
  return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
   
  // Given array
  int []arr = { 2, 5, 4, 3, 5, 4 };
   
  // Given size
  int size = arr.Length;
   
  // Function call
  Console.WriteLine(MinimumNoOfOperations(
    arr, size));
}
}
 
// This code is contributed by Stream_Cipher

<script>
// Javascript program for the above approach
 
// Function to print the minimum number of
// decrements to make all elements equals
function MinimumNoOfOperations(arr, n)
{
 
    // Find minimum element
    var min_ele = 1000000000;
    for (var i = 0; i < n; ++i) {
        min_ele = Math.min(min_ele, arr[i]);
    }
 
    // Stores frequencies of array elements
    var mp = new Map();
 
    // Update frequencies in the Map
    for (var i = 0; i < n; ++i) {
 
        if (arr[i] == min_ele)
            continue;
        else
        {
            if(mp.has(arr[i]))
            {
                mp.set(arr[i], mp.get(arr[i])+1);
            }
            else
            {
                mp.set(arr[i], 1);
            }
        }
    }
 
    // Stores the count of
    // decrements at each iteration
    var prev_val = 0;
 
    // Stores the total
    // count of decrements
    var ans = 0;
    var keys = [];
 
    mp.forEach((value, key) => {
        keys.push(key);
    });
    keys.sort((a,b)=>b-a);
    // Calculate the number of decrements
    keys.forEach(value => {
        ans += (mp.get(value) + prev_val);
        prev_val += mp.get(value);
    });
 
    // Return minimum operations
    return ans;
}
 
// Driver Code
// Given array
var arr = [2, 5, 4, 3, 5, 4];
// Given size
var size = arr.length
// Function call
document.write( MinimumNoOfOperations(
    arr, size));
 
</script>

11

Complejidad de tiempo: O(N) donde N es el tamaño de la array.
Espacio Auxiliar: O(N)