Retire las monedas mínimas de modo que la diferencia absoluta entre dos pilas sea menor que K

Dada una array, arr[] de tamaño N y un número entero K, lo que significa que hay N pilas de monedas y la i ^-ésima contiene arr[i] monedas. La tarea es ajustar el número de monedas en cada pila de modo que para dos pilas cualquiera, si a es la cantidad de monedas en la primera pila yb es la cantidad de monedas en la segunda pila, entonces |a – b| ≤ k . 
Uno puede quitar monedas de diferentes montones para disminuir el número de monedas en esos montones, pero no puede aumentar el número de monedas en un montón agregando más monedas. Encuentre el número mínimo de monedas que se retirarán para satisfacer la condición dada.

Ejemplos: 

Entrada: arr[] = {2, 2, 2, 2}, K = 0 
Salida: 0 
Para dos montones cualesquiera, la diferencia en el número de monedas es ≤ 0. 
Por lo tanto, no es necesario retirar ninguna moneda.
Entrada: arr[] = {1, 5, 1, 2, 5, 1}, K = 3 
Salida: 2 
Si quitamos una moneda de cada uno de los montones que contienen 
5 monedas, entonces para dos montones cualesquiera la diferencia absoluta 
en el número de monedas es ≤ 3. 

Planteamiento: Ya que no podemos aumentar el número de monedas en una pila. Por lo tanto, el número mínimo de monedas en cualquier pila seguirá siendo el mismo, ya que no se pueden quitar, y aumentarlas se sumará a las operaciones que debemos minimizar. Ahora, encuentre el mínimo de monedas en una pila, y para cada otra pila, si la diferencia entre las monedas en la pila actual y la pila mínima de monedas es mayor que K, entonces retire las monedas adicionales de la pila actual.

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 number
// of coins that need to be removed
int minimumCoins(int a[], int n, int k)
{
    // To store the coins needed to be removed
    int cnt = 0;
 
    // Minimum value from the array
    int minVal = *min_element(a, a + n);
 
    // Iterate over the array
    // and remove extra coins
    for (int i = 0; i < n; i++)
    {
        int diff = a[i] - minVal;
 
        // If the difference between
        //  the current pile and the
        // minimum coin pile is greater than k
        if (diff > k)
        {
 
            // Count the extra coins to be removed
            cnt += (diff - k);
        }
    }
 
    // Return the required count
    return cnt;
}
 
// Driver code
int main()
{
    int a[] = { 1, 5, 1, 2, 5, 1 };
    int n = sizeof(a) / sizeof(a[0]);
    int k = 3;
 
    cout << minimumCoins(a, n, k);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG {
 
    // Function to return the minimum number
    // of coins that need to be removed
    static int min_val(int[] a)
    {
        int min = 2147483647;
        for (int el : a) {
            if (el < min) {
                min = el;
            }
        }
        return min;
    }
    static int minimumCoins(int a[], int n, int k)
    {
        // To store the coins needed to be removed
        int cnt = 0;
 
        // Minimum value from the array
        int minVal = min_val(a);
 
        // Iterate over the array and remove extra coins
        for (int i = 0; i < n; i++) {
            int diff = a[i] - minVal;
 
            // If the difference between the current pile
            // and the minimum coin pile is greater than k
            if (diff > k) {
                // Count the extra coins to be removed
                cnt += (diff - k);
            }
        }
 
        // Return the required count
        return cnt;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int a[] = { 1, 5, 1, 2, 5, 1 };
        int n = a.length;
        int k = 3;
        System.out.println(minimumCoins(a, n, k));
    }
}
 
// This code is contributed by jit_t

# Python implementation of the approach
 
# Function to return the minimum number
# of coins that need to be removed
def minimumCoins(a, n, k):
    # To store the coins needed to be removed
    cnt = 0;
 
    # Minimum value from the array
    minVal = min(a);
 
    # Iterate over the array and remove extra coins
    for i in range(n):
        diff = a[i] - minVal;
 
        # If the difference between the current pile and
        # the minimum coin pile is greater than k
        if (diff > k):
            # Count the extra coins to be removed
            cnt += (diff - k);
    # Return the required count
    return cnt;
 
# Driver code
a = [1, 5, 1, 2, 5, 1];
n = len(a);
k = 3;
print(minimumCoins(a, n, k));
 
     
# This code is contributed by 29AjayKumar

// C# implementation of the approach
using System;
 
class GFG {
   
   
    // Function to return the minimum number
    // of coins that need to be removed
    static int min_val(int[] a, int n)
    {
        int min = 2147483647;
        for (int i = 0;i<n;i++)
        {
            int el = a[i];
            if (el < min)
            {
                min = el;
            }
        }
        return min;
    }
 
    // Function to return the minimum number
    // of coins that need to be removed
    static int minimumCoins(int[] a, int n, int k)
    {
        // To store the coins needed to be removed
        int cnt = 0;
 
        // Minimum value from the array
        int minVal = min_val(a, n);
 
        // Iterate over the array and remove extra coins
        for (int i = 0; i < n; i++)
        {
            int diff = a[i] - minVal;
 
            // If the difference between the current pile
            // and the minimum coin pile is greater than k
            if (diff > k)
            {
                // Count the extra coins to be removed
                cnt += (diff - k);
            }
        }
 
        // Return the required count
        return cnt;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int[] a = { 1, 5, 1, 2, 5, 1 };
        int n = a.Length;
        int k = 3;
        Console.WriteLine(minimumCoins(a, n, k));
    }
}
 
/* This code is contributed by PrinciRaj1992 */

<script>
 
    // Javascript implementation of the approach
     
    // Function to return the minimum number
    // of coins that need to be removed
    function min_val(a, n)
    {
        let min = 2147483647;
        for (let i = 0;i<n;i++)
        {
            let el = a[i];
            if (el < min)
            {
                min = el;
            }
        }
        return min;
    }
  
    // Function to return the minimum number
    // of coins that need to be removed
    function minimumCoins(a, n, k)
    {
        // To store the coins needed to be removed
        let cnt = 0;
  
        // Minimum value from the array
        let minVal = min_val(a, n);
  
        // Iterate over the array and remove extra coins
        for (let i = 0; i < n; i++)
        {
            let diff = a[i] - minVal;
  
            // If the difference between the current pile
            // and the minimum coin pile is greater than k
            if (diff > k)
            {
                // Count the extra coins to be removed
                cnt += (diff - k);
            }
        }
  
        // Return the required count
        return cnt;
    }
     
    let a = [ 1, 5, 1, 2, 5, 1 ];
    let n = a.length;
    let k = 3;
    document.write(minimumCoins(a, n, k));
 
</script>

2

Complejidad de tiempo: O(n), donde n es el tamaño de la array
Espacio auxiliar: O(1), ya que no se utiliza espacio adicional