Minimice el incremento o incremento y decremento de Par para hacer que todos los elementos del Array sean iguales

Dada una array arr[] de tamaño N , la tarea es minimizar el número de pasos para hacer que todos los elementos de la array sean iguales realizando las siguientes operaciones:

1. Elige un elemento de la array y auméntalo en 1.
2. Seleccione dos elementos simultáneamente (arr[i], arr[j]) aumente arr[i] en 1 y disminuya arr[j] en 1.

Ejemplos :

Entrada: arr = [4, 2, 4, 6]
Salida: 2
Explicación : Realice la operación 2 en los elementos 2 y 6 de la array. 
Por lo tanto, aumentar 2 en 2 y disminuir 6 en 2 hace que todos los elementos de la array sean iguales.

Entrada: arr = [1, 2, 3, 4]
Salida: 3
Explicación: Incrementar 1 por 1 una vez. array[] = {2, 2, 3, 4}.
Luego aumente 1 en 1 y disminuya 4 en 1 en un solo paso. arr[] = {3, 2, 3, 3}
Incrementa 2 en 1. arr[] = {3, 3, 3, 3}. Entonces operaciones totales = 3.

Enfoque: este problema se puede resolver utilizando el enfoque codicioso basado en la siguiente idea:

Para minimizar la cantidad de pasos, haga que todos sean iguales al techo (promedio) de todos los elementos de la array. Para hacer esto, aumente simultáneamente los elementos menores y disminuya los elementos mayores tanto como sea posible y luego incremente solo los elementos menores.

Siga los pasos que se mencionan a continuación para resolver el problema:

• Ordenar la array.
• Averigüe el techo del promedio de la array (digamos avg ).
• Ahora recorra la array de i = 0 a N-1 :
  • Siempre que encuentre algún elemento más pequeño que el promedio.
    • Recorra desde el extremo posterior de la array y deduzca los elementos que son mayores que el promedio.
    • Finalmente, agregue avg-a[i] a la respuesta.
• Devuelve la respuesta.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
 
// function to find the minimum operations
// to make the array elements same
int findMinOperations(vector<int> a, int n)
{
    ll avg = 0;
 
    // Sorting the array
    sort(a.begin(), a.end());
    for (int i : a) {
        avg += i;
    }
 
    // Finding out the average
 
    avg = avg % n == 0 ? avg / n : avg / n + 1;
    int i = 0, j = n - 1;
    int ans = 0;
 
    // Traversing the array
    while (i <= j) {
 
        // If current element is less than avg
        if (a[i] < avg) {
 
            // Total increments needed
            int incrementNeeded = avg - a[i];
            int k = incrementNeeded;
            a[i] = avg;
 
            // Traversing in the right side
            // of the array to find elements
            // which needs to be deduced to avg
            while (j > i && k > 0
                   && a[j] > avg) {
                int decrementNeeded
                    = a[j] - avg;
                if (k <= decrementNeeded) {
                    k -= decrementNeeded;
                }
                else {
                    a[j] -= k;
                    k = 0;
                }
                j--;
            }
 
            // Adding increments
            // needed to ans
            ans += incrementNeeded;
        }
        i++;
    }
    return ans;
}
 
// Driver Code
int main()
{
    vector<int> A;
    A = { 1, 2, 3, 4 };
    int N = A.size();
    cout << findMinOperations(A, N);
    return 0;
}

// Java code to implement the approach
import java.util.*;
public class GFG {
 
  // function to find the minimum operations
  // to make the array elements same
  static int findMinOperations(int[] a, int n)
  {
    long avg = 0;
 
    // Sorting the array
    Arrays.sort(a);
    for (int x = 0; x < a.length; x++) {
      avg += a[x];
    }
 
    // Finding out the average
    avg = avg % n == 0 ? avg / n : avg / n + 1;
    int i = 0, j = n - 1;
    int ans = 0;
 
    // Traversing the array
    while (i <= j) {
 
      // If current element is less than avg
      if (a[i] < avg) {
 
        // Total increments needed
        int incrementNeeded = (int)avg - a[i];
        int k = incrementNeeded;
        a[i] = (int)avg;
 
        // Traversing in the right side
        // of the array to find elements
        // which needs to be deduced to avg
        while (j > i && k > 0 && a[j] > avg) {
          int decrementNeeded = a[j] - (int)avg;
          if (k <= decrementNeeded) {
            k -= decrementNeeded;
          }
          else {
            a[j] -= k;
            k = 0;
          }
          j--;
        }
 
        // Adding increments
        // needed to ans
        ans += incrementNeeded;
      }
      i++;
    }
    return ans;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int[] A = { 1, 2, 3, 4 };
    int N = A.length;
    System.out.println(findMinOperations(A, N));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# Python code to implement the approach
 
# function to find the minimum operations
# to make the array elements same
def findMinOperations(a, n):
    avg = 0
 
    # sorting the array
    a = sorted(a)
    avg = sum(a)
    # finding the average of the array
    if avg % n == 0:
        avg = avg//n
    else:
        avg = avg//n + 1
    i = 0
    j = n-1
    ans = 0
 
    # traverse the array
    while i <= j:
 
        # if current element is less than avg
        if a[i] < avg:
 
            # total increment needed
            incrementNeeded = avg - a[i]
            k = incrementNeeded
            a[i] = avg
 
            # Traversing in the right side
            # of the array to find elements
            # which needs to be deducted to avg
            while j > i and k > 0 and a[j] > avg:
                decrementNeeded = a[j] - avg
                if k <= decrementNeeded:
                    k -= decrementNeeded
                else:
                    a[j] -= k
                    k = 0
 
                j -= 1
            # Adding increments
            # needed to ans
            ans += incrementNeeded
        i += 1
    return ans
 
 
# Driver code
if __name__ == '__main__':
    a = [1, 2, 3, 4]
    n = len(a)
    print(findMinOperations(a, n))
 
    # This code is contributed by Amnindersingg1414.

// C# code to implement the approach
using System;
class GFG
{
 
  // function to find the minimum operations
  // to make the array elements same
  static int findMinOperations(int []a, int n)
  {
    long avg = 0;
 
    // Sorting the array
    Array.Sort(a);
    for (int x = 0; x < a.Length; x++) {
      avg += a[x];
    }
 
    // Finding out the average
    avg = avg % n == 0 ? avg / n : avg / n + 1;
    int i = 0, j = n - 1;
    int ans = 0;
 
    // Traversing the array
    while (i <= j) {
 
      // If current element is less than avg
      if (a[i] < avg) {
 
        // Total increments needed
        int incrementNeeded = (int)avg - a[i];
        int k = incrementNeeded;
        a[i] = (int)avg;
 
        // Traversing in the right side
        // of the array to find elements
        // which needs to be deduced to avg
        while (j > i && k > 0
               && a[j] > avg) {
          int decrementNeeded
            = a[j] - (int)avg;
          if (k <= decrementNeeded) {
            k -= decrementNeeded;
          }
          else {
            a[j] -= k;
            k = 0;
          }
          j--;
        }
 
        // Adding increments
        // needed to ans
        ans += incrementNeeded;
      }
      i++;
    }
    return ans;
  }
 
  // Driver Code
  public static void Main()
  {
    int []A = { 1, 2, 3, 4 };
    int N = A.Length;
    Console.Write(findMinOperations(A, N));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
        // JavaScript code for the above approach
        let mod = 1000000007
 
        // function to find the minimum operations
        // to make the array elements same
        function findMinOperations(a, n) {
            let avg = 0;
 
            // Sorting the array
            a.sort()
            for (let i of a) {
                avg += i;
            }
 
            // Finding out the average
            avg = avg % n == 0 ? Math.floor(avg / n) : Math.floor(avg / n) + 1;
            let i = 0, j = n - 1;
            let ans = 0;
 
            // Traversing the array
            while (i <= j) {
 
                // If current element is less than avg
                if (a[i] < avg) {
 
                    // Total increments needed
                    let incrementNeeded = avg - a[i];
                    let k = incrementNeeded;
                    a[i] = avg;
 
                    // Traversing in the right side
                    // of the array to find elements
                    // which needs to be deduced to avg
                    while (j > i && k > 0
                        && a[j] > avg) {
                        let decrementNeeded
                            = a[j] - avg;
                        if (k <= decrementNeeded) {
                            k -= decrementNeeded;
                        }
                        else {
                            a[j] -= k;
                            k = 0;
                        }
                        j--;
                    }
 
                    // Adding increments
                    // needed to ans
                    ans += incrementNeeded;
                }
                i++;
            }
            return ans;
        }
 
        // Driver Code
        let A;
        A = [1, 2, 3, 4];
        let N = A.length;
        document.write(findMinOperations(A, N));
 
   // This code is contributed by Potta Lokesh
 
    </script>

3

Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)