Número mínimo de operaciones de incremento-otras para hacer que todos los elementos de la array sean iguales.

Nos dan una array que consta de n elementos. En cada operación, puede seleccionar cualquier elemento y aumentar el resto de n-1 elementos en 1. Debe hacer que todos los elementos sean iguales realizando dicha operación tantas veces como desee. Encuentre el número mínimo de operaciones necesarias para esto.

Ejemplos: 

Input : arr[] = {1, 2, 3}
Output : Minimum Operation = 3
Explanation : 
operation | increased elements | after increment
    1     |    1, 2            | 2, 3, 3
    2     |    1, 2            | 3, 4, 3
    3     |    1, 3            | 4, 4, 4

Input : arr[] = {4, 3, 4}
Output : Minimum Operation = 2
Explanation : 
operation | increased elements | after increment
     1    |    1, 2           | 5, 4, 4
     2    |    2, 3           | 5, 5, 5

Fuerza bruta: una forma simple de hacer que todos los elementos sean iguales es que en cada paso encuentre los elementos más grandes y luego aumente todos los elementos restantes n-1 en 1. Debemos seguir haciendo esta operación hasta que todos los elementos sean iguales. Complejidad de tiempo: O (n ^ 2)

Mejor enfoque: si observamos más de cerca cada operación y la declaración del problema, encontraremos que aumentar todos los elementos n-1 excepto el más grande es similar a disminuir solo el elemento más grande. Por lo tanto, los elementos más pequeños no necesitan disminuir más y el resto de los elementos disminuirán hasta el más pequeño. De esta forma, el número total de operaciones requeridas para hacer que todos los elementos sean iguales será arraySum – n * (smallestElement). La complejidad del tiempo será la misma que la de encontrar los elementos más pequeños y la suma de la array, es decir, O (n). 

// find array sum
sum = arraySum (int arr[], int n);

// find the smallest element from array
small = smallest (int arr, int n);

// calculate min operation required
minOperation = sum - (n * small);

// return result
return minOperation;

Implementación:

// CPP for finding minimum operation required
#include <bits/stdc++.h>
using namespace std;
 
// function for finding array sum
int arraySum(int arr[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
    return sum;
}
 
// function for finding smallest element
int smallest(int arr[], int n)
{
    int small = INT_MAX;
    for (int i = 0; i < n; i++)
        if (arr[i] < small)
            small = arr[i];
    return small;
}
 
// function for finding min operation
int minOp(int arr[], int n)
{
    // find array sum
    int sum = arraySum(arr, n);
    // find the smallest element from array
    int small = smallest(arr, n);
    // calculate min operation required
    int minOperation = sum - (n * small);
    // return result
    return minOperation;
}
 
// driver function
int main()
{
    int arr[] = { 5, 6, 2, 4, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum Operation = " << minOp(arr, n);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

// [STL] - CPP for finding minimum operation required
#include<bits/stdc++.h>
using namespace std;
 
// function for finding min operation
int minOp (int arr[], int n)
{
    // find array sum
    int sum = accumulate(arr,arr+n,0);
    // find the smallest element from array
    int small = *min_element(arr,arr+n);
    // calculate min operation required
    int minOperation = sum - (n * small);
    // return result
    return minOperation;
}
 
//driver function
int main()
{
    int arr[] = {5, 6, 2, 4, 3};
    int n = sizeof(arr)/ sizeof(arr[0]);
    cout << "Minimum Operation = " << minOp (arr, n);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

// C for finding minimum operation required
#include <limits.h>
#include <stdio.h>
 
// function for finding array sum
int arraySum(int arr[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
    return sum;
}
 
// function for finding smallest element
int smallest(int arr[], int n)
{
    int small = INT_MAX;
    for (int i = 0; i < n; i++)
        if (arr[i] < small)
            small = arr[i];
    return small;
}
 
// function for finding min operation
int minOp(int arr[], int n)
{
    // find array sum
    int sum = arraySum(arr, n);
    // find the smallest element from array
    int small = smallest(arr, n);
    // calculate min operation required
    int minOperation = sum - (n * small);
    // return result
    return minOperation;
}
 
// driver function
int main()
{
    int arr[] = { 5, 6, 2, 4, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Minimum Operation = %d", minOp(arr, n));
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

// Java program to find min operation
import java.io.*;
 
class minOperation {
    // Function to print minimum operation required to make
    // all elements of an array equal
    static void printMinOp(int arr[])
    {
        int arraySum, smallest, arr_size = arr.length;
        arraySum = 0;
        smallest = arr[0];
        for (int i = 0; i < arr_size; i++) {
            // If current element is smaller than update smallest
            if (arr[i] < smallest)
                smallest = arr[i];
 
            // find array sum
            arraySum += arr[i];
        }
 
        int minOperation = arraySum - arr_size * smallest;
 
        // Print min operation required
        System.out.println("Minimum Operation = " + minOperation);
    }
 
    // Driver program to test above functions
    public static void main(String[] args)
    {
        int arr[] = { 5, 6, 2, 4, 3 };
        printMinOp(arr);
    }
}
 
// This code is contributed by Sania Kumari Gupta

# Python 3 for finding minimum
# operation required
 
# function for finding min
# operation
def minOp (arr, n) :
     
    # find array sum
    sm = sum(arr)
 
    # find the smallest element from
    # array
    small = min(arr)
 
    # calculate min operation required
    minOperation = sm - (n * small)
 
    # return result
    return minOperation
     
# Driver function
arr = [5, 6, 2, 4, 3]
n = len(arr)
print( "Minimum Operation = ", minOp (arr, n))
 
# This code is contributed by Shubham Singh

// C# program to find min operation
using System;
 
class GFG {
     
    /* Function to print minimum
    operation required to make all
    elements of an array equal */
    static void printMinOp(int []arr)
    {
        int arraySum, smallest,
        arr_size = arr.Length;
        arraySum = 0;
        smallest = arr[0];
         
        for (int i = 0; i < arr_size ; i ++)
        {
            /* If current element is
            smaller than update smallest */
            if (arr[i] < smallest)        
                smallest = arr[i];        
 
            /*find array sum */
            arraySum += arr[i];
        }
 
        int minOperation = arraySum - 
                        arr_size * smallest;
 
        /* Print min operation required */
        Console.Write("Minimum Operation = " +
                            minOperation);
    }
 
    /* Driver program to test above
    functions */
    public static void Main ()
    {
        int []arr = {5, 6, 2, 4, 3};
         
        printMinOp(arr);
    }
}
 
// This code is contributed by nitin mittal.

<?php
// PHP for finding minimum operation required
 
// function for finding array sum
function arraySum ($arr, $n)
{
    $sum = 0;
    for ($i = 0; $i < $n; $sum += $arr[$i++]);
    return $sum;
}
 
// function for finding smallest element
function smallest ($arr, $n)
{
    $small = PHP_INT_MAX;
    for ($i = 0; $i < $n; $i++)
        if ($arr[$i] < $small)
            $small = $arr[$i];
    return $small;
}
 
// function for finding min operation
function minOp ($arr, $n)
{
     
    // find array sum
    $sum = arraySum ($arr, $n);
 
    // find the smallest
    // element from array
    $small = smallest ($arr, $n);
 
    // calculate min operation
    // required
    $minOperation = $sum - ($n * $small);
 
    // return result
    return $minOperation;
}
 
    // Driver Code
    $arr = array (5, 6, 2, 4, 3);
    $n = sizeof($arr);
    echo "Minimum Operation = " , minOp ($arr, $n);
     
// This code is contributed by m_kit
?>

<script>
// javascript program to find min operationclass minOeration{
    /*
     * Function to print minimum operation
     required to make all elements of an array
     * equal
     */
    function printMinOp(arr)
    {
        var arraySum, smallest, arr_size = arr.length;
        arraySum = 0;
        smallest = arr[0];
        for (i = 0; i < arr_size; i++)
        {
         
            /*
             * If current element is smaller than update smallest
             */
            if (arr[i] < smallest)
                smallest = arr[i];
 
            /* find array sum */
            arraySum += arr[i];
        }
 
        var minOperation = arraySum - arr_size * smallest;
 
        /* Print min operation required */
        document.write("Minimum Operation = " + minOperation);
 
    }
 
    /* Driver program to test above functions */
        var arr = [ 5, 6, 2, 4, 3 ];
        printMinOp(arr);
 
// This code is contributed by aashish1995
</script>

Minimum Operation = 10

Complejidad de tiempo: O(N) , donde N representa el tamaño de la array dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.