Operaciones de incremento mínimo para igualar K elementos

Posted on by Rudeus Greyrat

Dada una array arr[] de N elementos y un entero K , la tarea es igualar cualquier K elemento de la array realizando solo operaciones de incremento, es decir, en una operación, cualquier elemento puede incrementarse en 1. Encuentre el número mínimo de operaciones requerida para hacer que cualquier K elementos sean iguales.
Ejemplos: 
 

Entrada: arr[] = {3, 1, 9, 100}, K = 3 
Salida: 14 
Incremente 3 seis veces y 1 ocho veces para un total de 
14 operaciones para hacer 3 elementos iguales a 9.
Entrada: arr[] = {5, 3, 10, 5}, K = 2 
Salida: 0 
No se requieren operaciones ya que el primer y el último 
elemento ya son iguales. 
 

 

Enfoque ingenuo: 
 

  1. Ordena la array en orden creciente.
  2. Ahora seleccione K elementos y hágalos iguales.
  3. Elija el valor i -ésimo como el valor más grande y haga que todos los elementos sean más pequeños que igual al elemento i -ésimo .
  4. Calcule el número de operaciones necesarias para hacer que los elementos K sean iguales al i -ésimo elemento para todos los i .
  5. La respuesta será la mínima de todas las posibilidades.

C++14

#include <bits/stdc++.h>
  
using namespace std;
  
int minOperations(vector<int> ar, int& n, int& k)
{
    // Sort the array in increasing order
    sort(ar.begin(), ar.end());
    int opsneeded, ans = INT_MAX;
  
    for (int i = k; i < n; i++) {
        opsneeded = 0;
  
        for (int j = i - k; j < i; j++)
            opsneeded += ar[i - 1] - ar[j];
  
        ans = min(ans, opsneeded);
    }
  
    return ans;
}
  
int main()
{
    vector<int> arr = { 3, 1, 9, 100 };
    int n = arr.size();
    int k = 3;
  
    cout << minOperations(arr, n, k);
  
    return 0;
}
// this code is contributed by prophet1999

Java

// JAVA code for the above approach
import java.util.*;
class GFG {
  public static int minOperations(ArrayList<Integer> ar,
                                  int n, int k)
  {
  
    // Sort the array in increasing order
    Collections.sort(ar);
    int opsneeded, ans = Integer.MAX_VALUE;
  
    for (int i = k; i < n; i++) {
      opsneeded = 0;
  
      for (int j = i - k; j < i; j++)
        opsneeded += ar.get(i - 1) - ar.get(j);
  
      ans = Math.min(ans, opsneeded);
    }
  
    return ans;
  }
  
  public static void main(String[] args)
  {
    ArrayList<Integer> arr = new ArrayList<Integer>(
      Arrays.asList(3, 1, 9, 100));
    int n = arr.size();
    int k = 3;
  
    System.out.print(minOperations(arr, n, k));
  }
}
  
// This code is contributed by Taranpreet
Producción

14

Complejidad de tiempo: depende de la clasificación, será O(n^2+n*K) u O(n log n+n*K)

Espacio auxiliar: depende de la clasificación, será O(n) u O(1)

Enfoque eficiente: el enfoque ingenuo se puede modificar para calcular las operaciones mínimas necesarias para hacer que los elementos K sean iguales al elemento i -ésimo más rápido que O(K) usando la técnica de la ventana deslizante en tiempo constante dado que las operaciones requeridas para hacer el 1er K se conocen los elementos iguales al K -ésimo elemento. Sean C las operaciones necesarias o el costo de hacer que los elementos en el rango [l, l + K – 1] sean iguales al (l + K – 1) ésimo elemento. Ahora para encontrar el costo del rango [l + 1, l + K]
, se puede utilizar la solución para el rango [l, l + K – 1] . 
Sea C’ el costo del rango [l + 1, l + K] . 
 

  1. Dado que incrementamos el l ésimo elemento a (l + K – 1) ésimo elemento, C incluye el elemento de costo (l + k – 1) – elemento (l) pero C’ no necesita incluir este costo. 
    Entonces, C’ = C – (elemento(l + k – 1) – elemento(l)) 
     
  2. Ahora C’ representa el costo de hacer que todos los elementos en el rango [l + 1, l + K – 1] sean iguales a (l + K – 1) el elemento th . 
    Dado que necesitamos hacer que todos los elementos sean iguales al (l + K) enésimo elemento en lugar del (l + K – 1) enésimo elemento, podemos incrementar estos k – 1 elementos al (l + K) enésimo elemento que hace C’ = C’ + (k – 1) * (elemento(l + k) – elemento(l + k -1))

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to return the minimum number of
// increment operations required to make
// any k elements of the array equal
int minOperations(vector<int> ar, int k)
{
    // Sort the array in increasing order
    sort(ar.begin(), ar.end());
  
    // Calculate the number of operations
    // needed to make 1st k elements equal to
    // the kth element i.e. the 1st window
    int opsNeeded = 0;
    for (int i = 0; i < k; i++) {
        opsNeeded += ar[k - 1] - ar[i];
    }
  
    // Answer will be the minimum of all
    // possible k sized windows
    int ans = opsNeeded;
  
    // Find the operations needed to make
    // k elements equal to ith element
    for (int i = k; i < ar.size(); i++) {
  
        // Slide the window to the right and
        // subtract increments spent on leftmost
        // element of the previous window
        opsNeeded = opsNeeded - (ar[i - 1] - ar[i - k]);
  
        // Add increments needed to make the 1st k-1
        // elements of this window equal to the
        // kth element of the current window
        opsNeeded += (k - 1) * (ar[i] - ar[i - 1]);
        ans = min(ans, opsNeeded);
    }
    return ans;
}
  
// Driver code
int main()
{
    vector<int> arr = { 3, 1, 9, 100 };
    int n = arr.size();
    int k = 3;
  
    cout << minOperations(arr, k);
  
    return 0;
}

Java

// Java implementation of the approach 
import java.util.Arrays; 
  
class geeksforgeeks {
  
// Function to return the minimum number of 
// increment operations required to make 
// any k elements of the array equal 
static int minOperations(int ar[], int k) 
{ 
    // Sort the array in increasing order 
    Arrays.sort(ar); 
  
    // Calculate the number of operations 
    // needed to make 1st k elements equal to 
    // the kth element i.e. the 1st window 
    int opsNeeded = 0; 
    for (int i = 0; i < k; i++) { 
        opsNeeded += ar[k - 1] - ar[i]; 
    } 
  
    // Answer will be the minimum of all 
    // possible k sized windows 
    int ans = opsNeeded; 
  
    // Find the operations needed to make 
    // k elements equal to ith element 
    for (int i = k; i < ar.length; i++) { 
  
        // Slide the window to the right and 
        // subtract increments spent on leftmost 
        // element of the previous window 
        opsNeeded = opsNeeded - (ar[i - 1] - ar[i - k]); 
  
        // Add increments needed to make the 1st k-1 
        // elements of this window equal to the 
        // kth element of the current window 
        opsNeeded += (k - 1) * (ar[i] - ar[i - 1]); 
        ans = Math.min(ans, opsNeeded); 
    } 
    return ans; 
} 
  
// Driver code 
public static void main(String[] args) 
{ 
    int[] arr = { 3, 1, 9, 100 }; 
    int n = arr.length; 
    int k = 3; 
  
    System.out.printf("%d",minOperations(arr, k)); 
} 
}
  
// This code is contributed by Atul_kumar_Shrivastava

Python3

# Python3 implementation of the approach
  
# Function to return the minimum number of
# increment operations required to make
# any k elements of the array equal
def minOperations(ar, k):
  
    # Sort the array in increasing order
    ar = sorted(ar)
  
    # Calculate the number of operations
    # needed to make 1st k elements equal to
    # the kth element i.e. the 1st window
    opsNeeded = 0
    for i in range(k):
        opsNeeded += ar[k - 1] - ar[i]
  
    # Answer will be the minimum of all
    # possible k sized windows
    ans = opsNeeded
  
    # Find the operations needed to make
    # k elements equal to ith element
    for i in range(k, len(ar)):
  
        # Slide the window to the right and
        # subtract increments spent on leftmost
        # element of the previous window
        opsNeeded = opsNeeded - (ar[i - 1] - ar[i - k])
  
        # Add increments needed to make the 1st k-1
        # elements of this window equal to the
        # kth element of the current window
        opsNeeded += (k - 1) * (ar[i] - ar[i - 1])
        ans = min(ans, opsNeeded)
  
    return ans
  
# Driver code
arr = [3, 1, 9, 100]
n = len(arr)
k = 3
  
print(minOperations(arr, k))
  
# This code is contributed by Mohit Kumar

C#

// C# implementation of the approach 
using System; 
  
class geeksforgeeks {
  
// Function to return the minimum number of 
// increment operations required to make 
// any k elements of the array equal 
static int minOperations(int[] ar, int k) 
{ 
    // Sort the array in increasing order 
    Array.Sort(ar); 
  
    // Calculate the number of operations 
    // needed to make 1st k elements equal to 
    // the kth element i.e. the 1st window 
    int opsNeeded = 0; 
    for (int i = 0; i < k; i++) { 
        opsNeeded += ar[k - 1] - ar[i]; 
    } 
  
    // Answer will be the minimum of all 
    // possible k sized windows 
    int ans = opsNeeded; 
  
    // Find the operations needed to make 
    // k elements equal to ith element 
    for (int i = k; i < ar.Length; i++) { 
  
        // Slide the window to the right and 
        // subtract increments spent on leftmost 
        // element of the previous window 
        opsNeeded = opsNeeded - (ar[i - 1] - ar[i - k]); 
  
        // Add increments needed to make the 1st k-1 
        // elements of this window equal to the 
        // kth element of the current window 
        opsNeeded += (k - 1) * (ar[i] - ar[i - 1]); 
        ans = Math.Min(ans, opsNeeded); 
    } 
    return ans; 
} 
  
// Driver code 
public static void Main() 
{ 
    int[] arr = { 3, 1, 9, 100 }; 
    int n = arr.Length; 
    int k = 3; 
  
    Console.Write(minOperations(arr, k)); 
} 
}
  
// This code is contributed by AbhiThakur

JavaScript

<script>
  
// JavaScript implementation of the approach 
  
// Function to return the minimum number of 
// increment operations required to make 
// any k elements of the array equal 
function minOperations(ar,k)
{
    // Sort the array in increasing order 
    ar.sort(function(a,b){return a-b});
    
    // Calculate the number of operations 
    // needed to make 1st k elements equal to 
    // the kth element i.e. the 1st window 
    let opsNeeded = 0; 
    for (let i = 0; i < k; i++) { 
        opsNeeded += ar[k - 1] - ar[i]; 
    } 
    
    // Answer will be the minimum of all 
    // possible k sized windows 
    let ans = opsNeeded; 
    
    // Find the operations needed to make 
    // k elements equal to ith element 
    for (let i = k; i < ar.length; i++) { 
    
        // Slide the window to the right and 
        // subtract increments spent on leftmost 
        // element of the previous window 
        opsNeeded = opsNeeded - (ar[i - 1] - ar[i - k]); 
    
        // Add increments needed to make the 1st k-1 
        // elements of this window equal to the 
        // kth element of the current window 
        opsNeeded += (k - 1) * (ar[i] - ar[i - 1]); 
        ans = Math.min(ans, opsNeeded); 
    } 
    return ans; 
}
  
// Driver code 
let arr=[3, 1, 9, 100 ];
let n = arr.length; 
let k = 3; 
document.write(minOperations(arr, k));
  
  
// This code is contributed by patel2127
  
</script>
Producción

14

Complejidad de tiempo: depende de la clasificación, será O (n ^ 2) u O (n log n)

Espacio auxiliar: depende de la clasificación, será O(n) u O(1)
 

Publicación traducida automáticamente

Artículo escrito por KartikArora y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *