Dada una array arr[] de tamaño N, la tarea es imprimir el número mínimo de movimientos necesarios para igualar todos los elementos de la array seleccionando dos índices distintos y luego incrementar el elemento en el primer índice seleccionado y disminuir el elemento en el otro. índice seleccionado por 1 en cada movimiento. Si es imposible hacer que todos los elementos de la array sean iguales, imprima » -1 «.
Ejemplos :
Entrada: arr[] = {5, 4, 1, 10}
Salida: 5
Explicación:
Una de las formas posibles de realizar la operación es:
Operación 1: Seleccione los índices 1 y 3 y luego incremente arr[1] en 1 y disminuya arr[3] por 1. A partir de entonces, la array se modifica a {5, 5, 1, 9}.
Operación 2: seleccione los índices 2 y 3 y luego incremente arr[2] en 1 y disminuya arr[3] en 1. A partir de entonces, la array se modifica a {5, 5, 2, 8}.
Operación 3: seleccione los índices 2 y 3 y luego incremente arr[2] en 1 y disminuya arr[3] en 1. A partir de entonces, la array se modifica a {5, 5, 3, 7}.
Operación 4: seleccione los índices 2 y 3 y luego incremente arr[2] en 1 y disminuya arr[3] en 1. A partir de entonces, la array se modifica a {5, 5, 4, 6}.
Operación 5: seleccione los índices 2 y 3 y luego incremente arr[2] en 1 y disminuya arr[3] en 1. A partir de entonces, la array se modifica a {5, 5, 5, 5}.
Por lo tanto, el número total de movimientos necesarios es 5. Además, es el mínimo posible de movimientos necesarios.Entrada: arr[] = {1, 4}
Salida: -1
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Se puede observar que en un movimiento la suma de la array sigue siendo la misma, por lo tanto, si la suma de la array no es divisible por N , entonces es imposible hacer que todos los elementos de la array sean iguales.
- De lo contrario, cada elemento de la array será igual a la suma de la array dividida por N.
- Por lo tanto, la idea es usar la técnica de dos punteros para encontrar el número mínimo de movimientos necesarios para que todos los elementos del arreglo sean iguales a la suma/N .
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans como 0 , para almacenar el recuento de los movimientos necesarios.
- Encuentre la suma de la array y guárdela en una variable, digamos sum .
- Ahora, si la suma no es divisible por N , imprima » -1 «. De lo contrario, actualice la suma como sum =sum/N.
- Ordene la array en orden ascendente.
- Inicialice las variables, diga i como 0 y j como N – 1 para iterar sobre la array.
- Iterar hasta que i sea menor que j y realizar los siguientes pasos:
- Si aumentar arr[i] a sum es menor que disminuir arr[j] a sum , agregue sum – arr[i] a ans y luego actualice arr[i] y arr[j] y luego incremente i en 1 .
- De lo contrario, agregue arr[j] – sum a ans y actualice arr[i] y arr[j] y luego disminuya j en 1.
- Finalmente, después de completar los pasos anteriores, imprima el valor de almacenado en ans .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach
#include <algorithm>
#include <iostream>
using namespace std;
// Function to find the minimum
// operations to make the array
// elements equal
int find(int arr[], int N)
{
// Stores the sum of the
// array
int Sum = 0;
for (int i = 0; i < N; i++) {
Sum += arr[i];
}
if (Sum % N) {
return -1;
}
// update sum
Sum /= N;
// sort array
sort(arr, arr + N);
// Store the minimum
// needed moves
int ans = 0;
int i = 0, j = N - 1;
// Iterate until i
// is less than j
while (i < j) {
if (Sum - arr[i] < arr[j] - Sum) {
// Increment ans by
// Sum-arr[i]
ans += (Sum - arr[i]);
// update
arr[i] += (Sum - arr[i]);
arr[j] -= (Sum - arr[i]);
// Increment i by 1
i++;
}
else {
// Increment ans by
//arr[j]-Sum
ans += (arr[j] - Sum);
// Update
arr[i] += (arr[j] - Sum);
arr[j] -= (arr[j] - Sum);
// Decrement j by 1
j--;
}
}
// Return the value in ans
return ans;
}
// Driver code
int main()
{
// Given input
int arr[] = { 5, 4, 1, 10 };
int N = sizeof(arr) / sizeof(int);
// Function call
cout << find(arr, N);
return 0;
}
// This code is contributed by Parth Manchanda
Java
import java.util.Arrays;
// Java Program for the above approach
class GFG {
// Function to find the minimum
// operations to make the array
// elements equal
public static int find(int arr[], int N)
{
// Stores the sum of the
// array
int Sum = 0;
for (int i = 0; i < N; i++) {
Sum += arr[i];
}
if (Sum % N > 0) {
return -1;
}
// update sum
Sum /= N;
// sort array
Arrays.sort(arr);
// Store the minimum
// needed moves
int ans = 0;
int i = 0, j = N - 1;
// Iterate until i
// is less than j
while (i < j) {
if (Sum - arr[i] < arr[j] - Sum) {
// Increment ans by
// Sum-arr[i]
ans += (Sum - arr[i]);
// update
arr[i] += (Sum - arr[i]);
arr[j] -= (Sum - arr[i]);
// Increment i by 1
i++;
} else {
// Increment ans by
// arr[j]-Sum
ans += (arr[j] - Sum);
// Update
arr[i] += (arr[j] - Sum);
arr[j] -= (arr[j] - Sum);
// Decrement j by 1
j--;
}
}
// Return the value in ans
return ans;
}
// Driver code
public static void main(String args[]) {
// Given input
int arr[] = { 5, 4, 1, 10 };
int N = arr.length;
// Function call
System.out.println(find(arr, N));
}
}
// This code is contributed by gfgking
Python3
# Python program for the above approach # Function to find the minimum # operations to make the array # elements equal def find(arr, N): # Stores the sum of the # array Sum = sum(arr) # If sum is not divisible # by N if Sum % N: return -1 else: # Update sum Sum //= N # Sort the array arr.sort() # Store the minimum # needed moves ans = 0 i = 0 j = N-1 # Iterate until i # is less than j while i < j: # If the Sum-arr[i] # is less than the # arr[j]-sum if Sum-arr[i] < arr[j]-Sum: # Increment ans by # Sum-arr[i] ans += Sum-arr[i] # Update arr[i] += Sum-arr[i] arr[j] -= Sum-arr[i] # Increment i by 1 i += 1 # Otherwise, else: # Increment ans by # arr[j]-Sum ans += arr[j]-Sum # Update arr[i] += arr[j]-Sum arr[j] -= arr[j]-Sum # Decrement j by 1 j -= 1 # Return the value in ans return ans # Driver Code if __name__ == '__main__': # Given Input arr = [5, 4, 1, 10] N = len(arr) # Function Call print(find(arr, N))
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum
// operations to make the array
// elements equal
public static int find(int[] arr, int N)
{
// Stores the sum of the
// array
int Sum = 0;
int i = 0;
for(i = 0; i < N; i++)
{
Sum += arr[i];
}
if (Sum % N > 0)
{
return -1;
}
// update sum
Sum /= N;
// sort array
Array.Sort(arr);
// Store the minimum
// needed moves
int ans = 0;
i = 0;
int j = N - 1;
// Iterate until i
// is less than j
while (i < j)
{
if (Sum - arr[i] < arr[j] - Sum)
{
// Increment ans by
// Sum-arr[i]
ans += (Sum - arr[i]);
// update
arr[i] += (Sum - arr[i]);
arr[j] -= (Sum - arr[i]);
// Increment i by 1
i++;
}
else
{
// Increment ans by
// arr[j]-Sum
ans += (arr[j] - Sum);
// Update
arr[i] += (arr[j] - Sum);
arr[j] -= (arr[j] - Sum);
// Decrement j by 1
j--;
}
}
// Return the value in ans
return ans;
}
// Driver code
static public void Main()
{
// Given input
int[] arr = { 5, 4, 1, 10 };
int N = arr.Length;
// Function call
Console.WriteLine(find(arr, N));
}
}
// This code is contributed by target_2
Javascript
<script>
// JavaScript Program for the above approach
// Function to find the minimum
// operations to make the array
// elements equal
function find(arr, N) {
// Stores the sum of the
// array
let Sum = 0;
for (i = 0; i < arr.length; i++) {
Sum = Sum + arr[i];
}
// If sum is not divisible
// by N
if (Sum % N)
return -1;
else {
// Update sum
Sum = Math.floor(Sum / N);
// Sort the array
arr.sort(function (a, b) { return a - b });
// Store the minimum
// needed moves
ans = 0
i = 0
j = N - 1
// Iterate until i
// is less than j
while (i < j) {
// If the Sum-arr[i]
// is less than the
// arr[j]-sum
if (Sum - arr[i] < arr[j] - Sum) {
// Increment ans by
// Sum-arr[i]
ans += Sum - arr[i]
// Update
arr[i] += Sum - arr[i]
arr[j] -= Sum - arr[i]
// Increment i by 1
i += 1
}
// Otherwise,
else {
// Increment ans by
// arr[j]-Sum
ans += arr[j] - Sum
// Update
arr[i] += arr[j] - Sum
arr[j] -= arr[j] - Sum
// Decrement j by 1
j -= 1
}
}
}
// Return the value in ans
return ans;
}
// Driver Code
// Given Input
let arr = [5, 4, 1, 10];
let N = arr.length;
// Function Call
document.write(find(arr, N));
// This code is contributed by Potta Lokesh
</script>
5
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por harshitkap00r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA