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 = 11Entrada: 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:
- 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.
- Ordene el mapa en orden decreciente según las claves.
- Inicialice dos variables ans y prev_val con 0 para almacenar la respuesta actual y el prefijo sum respectivamente.
- Ahora itere el Mapa y agregue las frecuencias correspondientes de cada elemento junto con prev_val a ans como ans = ans + (freq) + prev_val
- Mientras itera el Mapa , incremente prev_val cada vez por la frecuencia del elemento actual.
- 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++
// 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
// 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
# 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#
// 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
Javascript
<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>
Producción:
11
Complejidad de tiempo: O(N) donde N es el tamaño de la array.
Espacio Auxiliar: O(N)