Dada una array arr[] que consta de N enteros positivos, la tarea es hacer que todos los elementos de la array sean iguales restando repetidamente 1 de cualquier número de elementos de la array y añadiéndolo a uno de los elementos adyacentes al mismo tiempo. Si no se pueden hacer iguales todos los elementos de la array, imprima «-1» . De lo contrario, imprima el recuento mínimo de operaciones requeridas.
Ejemplos:
Entrada: arr[] = {1, 0, 5}
Salida: 3
Explicación:
Operación 1: restar arr[2](= 5) por 1 y sumarlo a arr[1](= 0). Por lo tanto, la array arr[] se modifica a {1, 1, 4}.
Operación 2: Resta arr[2](= 4) por 1 y súmalo a arr[1](= 1). Por lo tanto, la array arr[] se modifica a {1, 2, 3}.
Operación 3: Resta arr[2](= 3) y arr[1](= 2) por 1 y súmalo a arr[1](= 1) y arr[2](= 2) respectivamente. Por lo tanto, la array arr[] se modifica a {2, 2, 2}.Por lo tanto, el número mínimo de operaciones requeridas es de 3.
Entrada: arr[] = {0, 3, 0}
Salida: 2
Enfoque: El problema dado se puede resolver con base en la siguiente observación:
- Todos los elementos de la array pueden hacerse iguales si y solo si el valor de todos los elementos de la array es igual al promedio de la array .
- Dado que solo se puede restar 1 de un elemento de array a la vez, la cantidad mínima de movimientos es el máximo de la suma del prefijo de la array o la cantidad de movimientos necesarios para que cada elemento sea igual al promedio de la array.
Siga los pasos a continuación para resolver el problema:
- Calcule la suma de los elementos de la array arr[] , digamos S .
- Si la suma S no es divisible por N , imprima «-1» .
- De lo contrario, realice las siguientes operaciones:
- Almacene el promedio de los elementos de la array en una variable, digamos avg .
- Inicialice dos variables, digamos total y cuente con 0 , para almacenar el resultado requerido y la suma de prefijos de movimientos mínimos para lograr el promedio respectivamente.
- Recorra la array dada arr[] y realice los siguientes pasos:
- Agregue el valor de (arr[i] – avg) al conteo .
- Actualice el valor de total al máximo del valor absoluto de count , total , (arr[i] – avg) .
- Después de completar el paso anterior, imprima el valor del total como la operación mínima requerida 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 find the minimum number
// of moves required to make all array
// elements equal
int findMinMoves(int arr[], int N)
{
// Store the total sum of the array
int sum = 0;
// Calculate total sum of the array
for (int i = 0; i < N; i++)
sum += arr[i];
// If the sum is not divisible
// by N, then print "-1"
if (sum % N != 0)
return -1;
// Stores the average
int avg = sum / N;
// Stores the count
// of operations
int total = 0;
int needCount = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Update number of moves
// required to make current
// element equal to avg
needCount += (arr[i] - avg);
// Update the overall count
total
= max(max(abs(needCount),
arr[i] - avg),
total);
}
// Return the minimum
// operations required
return total;
}
// Driver Code
int main()
{
int arr[] = { 1, 0, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findMinMoves(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to find the minimum number
// of moves required to make all array
// elements equal
static int findMinMoves(int[] arr, int N)
{
// Store the total sum of the array
int sum = 0;
// Calculate total sum of the array
for(int i = 0; i < N; i++)
sum += arr[i];
// If the sum is not divisible
// by N, then print "-1"
if (sum % N != 0)
return -1;
// Stores the average
int avg = sum / N;
// Stores the count
// of operations
int total = 0;
int needCount = 0;
// Traverse the array arr[]
for(int i = 0; i < N; i++)
{
// Update number of moves
// required to make current
// element equal to avg
needCount += (arr[i] - avg);
// Update the overall count
total = Math.max(
Math.max(Math.abs(needCount),
arr[i] - avg), total);
}
// Return the minimum
// operations required
return total;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 0, 5 };
int N = arr.length;
System.out.println(findMinMoves(arr, N));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to find the minimum number # of moves required to make all array # elements equal def findMinMoves(arr, N): # Store the total sum of the array sum = 0 # Calculate total sum of the array for i in range(N): sum += arr[i] # If the sum is not divisible # by N, then print "-1" if(sum % N != 0): return -1 # Stores the average avg = sum // N # Stores the count # of operations total = 0 needCount = 0 # Traverse the array arr[] for i in range(N): # Update number of moves # required to make current # element equal to avg needCount += (arr[i] - avg) # Update the overall count total = max(max(abs(needCount), arr[i] - avg), total) # Return the minimum # operations required return total # Driver Code if __name__ == '__main__': arr = [1, 0, 5] N = len(arr) print(findMinMoves(arr, N)) # This code is contributed by bgangwar59.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum number
// of moves required to make all array
// elements equal
static int findMinMoves(int[] arr, int N)
{
// Store the total sum of the array
int sum = 0;
// Calculate total sum of the array
for(int i = 0; i < N; i++)
sum += arr[i];
// If the sum is not divisible
// by N, then print "-1"
if (sum % N != 0)
return -1;
// Stores the average
int avg = sum / N;
// Stores the count
// of operations
int total = 0;
int needCount = 0;
// Traverse the array arr[]
for(int i = 0; i < N; i++)
{
// Update number of moves
// required to make current
// element equal to avg
needCount += (arr[i] - avg);
// Update the overall count
total = Math.Max(
Math.Max(Math.Abs(needCount),
arr[i] - avg), total);
}
// Return the minimum
// operations required
return total;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 0, 5 };
int N = arr.Length;
Console.Write(findMinMoves(arr, N));
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum number
// of moves required to make all array
// elements equal
function findMinMoves(arr, N)
{
// Store the total sum of the array
let sum = 0;
// Calculate total sum of the array
for(let i = 0; i < N; i++)
sum += arr[i];
// If the sum is not divisible
// by N, then print "-1"
if (sum % N != 0)
return -1;
// Stores the average
let avg = sum / N;
// Stores the count
// of operations
let total = 0;
let needCount = 0;
// Traverse the array arr[]
for(let i = 0; i < N; i++)
{
// Update number of moves
// required to make current
// element equal to avg
needCount += (arr[i] - avg);
// Update the overall count
total = Math.max(Math.max(
Math.abs(needCount),
arr[i] - avg), total);
}
// Return the minimum
// operations required
return total;
}
// Driver Code
let arr = [ 1, 0, 5 ];
let N = arr.length;
document.write(findMinMoves(arr, N))
// This code is contributed by Hritik
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rutvikchandla3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA