Dada una array arr[] que consta de N enteros positivos, la tarea es minimizar el número de operaciones requeridas para minimizar la diferencia absoluta entre los elementos más pequeños y más grandes presentes en la array . En cada operación, reste 1 de un elemento de array e incremente 1 a otro elemento de array.
Ejemplos:
Entrada: arr[] = {1, 6}
Salida: 2
Explicación:
A continuación se muestran las operaciones realizadas:
Operación 1: Restar 1 del segundo elemento y sumar 1 al primer elemento modifica la array a {2, 5}.
Operation2: Restar 1 del segundo elemento y agregar 1 al primer elemento modifica la array a {3, 4}.
Después de las operaciones anteriores, la diferencia absoluta entre el elemento mínimo y máximo es (4 – 3) = 1, que es el mínimo y el número de operaciones requeridas es 2.Entrada: arr[] = {1, 2, 2, 1, 1}
Salida: 0
Enfoque: el problema dado se puede resolver observando el hecho de que el incremento y la disminución de un elemento de la array en 1 se realizan en pares, por lo que si la suma del elemento de la array es divisible por N , entonces todos los elementos de la array pueden convertirse en sum/N . De lo contrario, algunos elementos tendrán el valor sum/N y algunos elementos tendrán el valor (sum/N + 1) después de realizar las operaciones dadas. Siga los pasos a continuación para resolver el problema dado:
- Inicialice una array auxiliar, digamos final[] que almacena la array resultante con la diferencia mínima requerida.
- Ordena la array dada en orden creciente .
- Recorra la array dada y si el índice actual i es menor que sum%N , actualice el elemento actual de la array final al valor (sum/N + 1) . De lo contrario, actualice final[i] a (sum/N) .
- Invierta la array final[] .
- Inicialice una variable, digamos ans = 0 que almacene el número mínimo de operaciones para convertir arr[] a final[] .
- Recorra las arrays arr[] y final[] simultáneamente y agregue el valor absoluto de la diferencia de arr[i] y final[i] a la variable ans .
- Después de completar los pasos anteriores, imprima el valor de ans/2 como la operación mínima resultante.
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 minimize the operations
// for the difference between minimum
// and maximum element by incrementing
// decrementing array elements in pairs
void countMinimumSteps(int arr[], int N)
{
// Stores the sum of the array
int sum = 0;
// Find the sum of array element
for (int i = 0; i < N; i++) {
sum += arr[i];
}
// Stores the resultant final array
int finalArray[N];
// Iterate over the range [0, N]
for (int i = 0; i < N; ++i) {
// Assign values to finalArray
if (i < sum % N) {
finalArray[i] = sum / N + 1;
}
else {
finalArray[i] = sum / N;
}
}
// Reverse the final array
reverse(finalArray, finalArray + N);
// Stores the minimum number of
// operations required
int ans = 0;
// Update the value of ans
for (int i = 0; i < N; ++i) {
ans += abs(arr[i] - finalArray[i]);
}
// Print the result
cout << ans / 2;
}
// Driver Code
int main()
{
int arr[] = { 1, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
countMinimumSteps(arr, N);
return 0;
}
Java
// Java program for the above approach
class GFG{
static void reverse(int a[], int n)
{
int i, k, t;
for(i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
}
// Function to minimize the operations
// for the difference between minimum
// and maximum element by incrementing
// decrementing array elements in pairs
static void countMinimumSteps(int arr[], int N)
{
// Stores the sum of the array
int sum = 0;
// Find the sum of array element
for(int i = 0; i < N; i++)
{
sum += arr[i];
}
// Stores the resultant final array
int finalArray[] = new int[N];
// Iterate over the range [0, N]
for(int i = 0; i < N; ++i)
{
// Assign values to finalArray
if (i < sum % N)
{
finalArray[i] = sum / N + 1;
}
else
{
finalArray[i] = sum / N;
}
}
// Reverse the final array
reverse(finalArray, finalArray.length);
// Stores the minimum number of
// operations required
int ans = 0;
// Update the value of ans
for(int i = 0; i < N; ++i)
{
ans += Math.abs(arr[i] - finalArray[i]);
}
// Print the result
System.out.println(ans / 2);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 6 };
int N = arr.length;
countMinimumSteps(arr, N);
}
}
// This code is contributed by abhinavjain194
Python3
# Python program for the above approach # Function to minimize the operations # for the difference between minimum # and maximum element by incrementing # decrementing array elements in pairs def countMinimumSteps(arr, N): # Stores the sum of the array sum = 0; # Find the sum of array element for i in range(N): sum += arr[i]; # Stores the resultant final array finalArray = [0] * N; # Iterate over the range [0, N] for i in range(0, N): #print(i) # Assign values to finalArray if (i < sum % N): finalArray[i] = (sum // N)+ 1; else: finalArray[i] = sum // N; # Reverse the final array finalArray = finalArray[::-1]; # Stores the minimum number of # operations required ans = 0; # Update the value of ans for i in range(N): ans += abs(arr[i] - finalArray[i]); # Print the result print(ans // 2); # Driver Code arr = [1, 6]; N = len(arr); countMinimumSteps(arr, N); # This code is contributed by _saurabh_jaiswal.
C#
// C# program for the above approach
using System;
class GFG{
static void reverse(int[] a, int n)
{
int i, t;
for(i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
}
// Function to minimize the operations
// for the difference between minimum
// and maximum element by incrementing
// decrementing array elements in pairs
static void countMinimumSteps(int[] arr, int N)
{
// Stores the sum of the array
int sum = 0;
// Find the sum of array element
for(int i = 0; i < N; i++)
{
sum += arr[i];
}
// Stores the resultant final array
int[] finalArray = new int[N];
// Iterate over the range [0, N]
for(int i = 0; i < N; ++i)
{
// Assign values to finalArray
if (i < sum % N)
{
finalArray[i] = sum / N + 1;
}
else
{
finalArray[i] = sum / N;
}
}
// Reverse the final array
reverse(finalArray, finalArray.Length);
// Stores the minimum number of
// operations required
int ans = 0;
// Update the value of ans
for(int i = 0; i < N; ++i)
{
ans += Math.Abs(arr[i] - finalArray[i]);
}
// Print the result
Console.WriteLine(ans / 2);
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 1, 6 };
int N = arr.Length;
countMinimumSteps(arr, N);
}
}
// This code is contributed by target_2
Javascript
<script>
// Javascript program for the above approach
// Function to minimize the operations
// for the difference between minimum
// and maximum element by incrementing
// decrementing array elements in pairs
function countMinimumSteps(arr, N)
{
// Stores the sum of the array
let sum = 0;
// Find the sum of array element
for (let i = 0; i < N; i++) {
sum += arr[i];
}
// Stores the resultant final array
let finalArray = new Array(N);
// Iterate over the range [0, N]
for (let i = 0; i < N; ++i) {
// Assign values to finalArray
if (i < sum % N) {
finalArray[i] = Math.floor(sum / N + 1);
}
else {
finalArray[i] = Math.floor(sum / N);
}
}
// Reverse the final array
finalArray.reverse();
// Stores the minimum number of
// operations required
let ans = 0;
// Update the value of ans
for (let i = 0; i < N; ++i) {
ans += Math.abs(arr[i] - finalArray[i]);
}
// Print the result
document.write(Math.floor(ans / 2));
}
// Driver Code
let arr = [1, 6];
let N = arr.length
countMinimumSteps(arr, N);
// This code is contributed by _saurabh_jaiswal.
</script>
2
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA