Dada una array arr[]. La tarea es minimizar el número de operaciones requeridas para hacer que todos los elementos en arr[] sean iguales. Se permite reemplazar cualquier elemento en arr[] con cualquier otro elemento casi una vez. Encuentre el número mínimo de operaciones requeridas para hacerlo, en una operación tome cualquier sufijo de arr[] e incremente/disminuya los valores en ese sufijo en 1 .
Ejemplos
Entrada : arr[] = {-1, 0, 2}
Salida: 1
Explicación : Las siguientes son las operaciones realizadas para hacer que todos los elementos en arr[] sean iguales.
Inicialmente, cambie el último elemento de la array a 0, por lo que arr[] = {-1, 0, 0}
Ahora, use la operación una vez en el sufijo que comienza en arr 2 , lo que significa que arr 2 y arr 3 se reducen en 1 . Por lo tanto, haciendo que todos los elementos de la array -1.
Por lo tanto, el número de operaciones es 1.Entrada : arr[] = {-3, -5, -2, 1 }
Salida : 4
Enfoque : Este problema está basado en la implementación. Siga los pasos a continuación para resolver el problema dado.
- Dado que no es necesario realizar ninguna operación en el sufijo que comienza en arr 1 , ya que eso puede cambiar todos los enteros en la array.
- Entonces, la única forma de hacer que arr i sea igual a arr i-1 es realizar una operación en el sufijo que comienza en a i , abs(a i −a i-1 ) veces.
- Ahora, la forma óptima de cambiar inicialmente un valor en la array es minimizar las operaciones.
- Para hacer que arr 1 sea igual a arr 2 , las operaciones mínimas se reducen en abs (arr 2 – arr 1 ) .
- De manera similar, para hacer que arr n sea igual a arr n-1 , operación = abs(arr n – arr n-1 ) .
- Para los elementos de la izquierda, cambiar cualquier elemento arr i afecta tanto a abs(a i −a i-1 ) como a abs(a i+1 −a i ) .
- Además, observe este hecho importante de que este valor se minimiza cuando a i está entre a i-1 y a i+1 , inclusive.
- Por lo tanto, el número de operaciones se reduce de abs(a i −a i-1 )+abs(a i+1 −a i ) a abs(a i+1 −a i-1 ) .
- Devuelve la respuesta final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
void findMinOperations(vector<int> ar, int n)
{
// Initializing vector to avoid overflows
vector<int> arr(n + 5);
for (int i = 1; i <= n; i++) {
arr[i] = ar[i - 1];
}
int result = 0;
// Calculating minimum operations to be
// performed on initial array
for (int i = 2; i <= n; i++) {
result += abs(arr[i] - arr[i - 1]);
}
// Way to change a value to make
// a1 equal to a2 or a(n)
// equal to a(n-1)
int max_operations
= max(abs(arr[1] - arr[2]),
abs(arr[n] - arr[n - 1]));
for (int i = 2; i < n; i++) {
// For the rest of elements
// taking the max of
// operations already done +
// the ones performed here
max_operations
= max(
max_operations,
abs(arr[i] - arr[i - 1])
+ abs(arr[i + 1] - arr[i])
- abs(arr[i + 1] - arr[i - 1]));
}
// Print the final result
cout << result - max_operations << "\n";
}
// Driver Code
int main()
{
int N = 3;
vector<int> arr = { -1, 0, 2 };
findMinOperations(arr, N);
return 0;
}
Java
// Java program for above approach
class GFG {
static void findMinOperations(int[] ar, int n) {
// Initializing vector to avoid overflows
int[] arr = new int[n + 5];
for (int i = 1; i <= n; i++) {
arr[i] = ar[i - 1];
}
int result = 0;
// Calculating minimum operations to be
// performed on initial array
for (int i = 2; i <= n; i++) {
result += Math.abs(arr[i] - arr[i - 1]);
}
// Way to change a value to make
// a1 equal to a2 or a(n)
// equal to a(n-1)
int max_operations = Math.max(Math.abs(arr[1] - arr[2]),
Math.abs(arr[n] - arr[n - 1]));
for (int i = 2; i < n; i++) {
// For the rest of elements
// taking the max of
// operations already done +
// the ones performed here
max_operations = Math.max(
max_operations,
Math.abs(arr[i] - arr[i - 1])
+ Math.abs(arr[i + 1] - arr[i])
- Math.abs(arr[i + 1] - arr[i - 1]));
}
// Print the final result
System.out.println(result - max_operations);
}
// Driver Code
public static void main(String args[]) {
int N = 3;
int[] arr = { -1, 0, 2 };
findMinOperations(arr, N);
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# Python code for the above approach def findMinOperations(ar, n): # Initializing vector to avoid overflows arr = [0] * (n + 5) for i in range(1, n + 1): arr[i] = ar[i - 1] result = 0 # Calculating minimum operations to be # performed on initial array for i in range(2, n + 1): result += abs(arr[i] - arr[i - 1]) # Way to change a value to make # a1 equal to a2 or a(n) # equal to a(n-1) max_operations = max(abs(arr[1] - arr[2]), abs(arr[n] - arr[n - 1])) for i in range(2, n): # For the rest of elements # taking the max of # operations already done + # the ones performed here max_operations = max( max_operations, abs(arr[i] - arr[i - 1]) + abs(arr[i + 1] - arr[i]) - abs(arr[i + 1] - arr[i - 1])) # Print the final result print((result - max_operations)) # Driver Code N = 3 arr = [-1, 0, 2] findMinOperations(arr, N) # This code is contributed by gfgking
C#
// C# program to implement
// the above approach
using System;
class GFG
{
static void findMinOperations(int[] ar, int n) {
// Initializing vector to avoid overflows
int[] arr = new int[n + 5];
for (int i = 1; i <= n; i++) {
arr[i] = ar[i - 1];
}
int result = 0;
// Calculating minimum operations to be
// performed on initial array
for (int i = 2; i <= n; i++) {
result += Math.Abs(arr[i] - arr[i - 1]);
}
// Way to change a value to make
// a1 equal to a2 or a(n)
// equal to a(n-1)
int max_operations = Math.Max(Math.Abs(arr[1] - arr[2]),
Math.Abs(arr[n] - arr[n - 1]));
for (int i = 2; i < n; i++) {
// For the rest of elements
// taking the max of
// operations already done +
// the ones performed here
max_operations = Math.Max(
max_operations,
Math.Abs(arr[i] - arr[i - 1])
+ Math.Abs(arr[i + 1] - arr[i])
- Math.Abs(arr[i + 1] - arr[i - 1]));
}
// Print the final result
Console.Write(result - max_operations);
}
// Driver Code
public static void Main()
{
int N = 3;
int[] arr = { -1, 0, 2 };
findMinOperations(arr, N);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript code for the above approach
function findMinOperations(ar, n) {
// Initializing vector to avoid overflows
let arr = new Array(n + 5);
for (let i = 1; i <= n; i++) {
arr[i] = ar[i - 1];
}
let result = 0;
// Calculating minimum operations to be
// performed on initial array
for (let i = 2; i <= n; i++) {
result += Math.abs(arr[i] - arr[i - 1]);
}
// Way to change a value to make
// a1 equal to a2 or a(n)
// equal to a(n-1)
let max_operations
= Math.max(Math.abs(arr[1] - arr[2]),
Math.abs(arr[n] - arr[n - 1]));
for (let i = 2; i < n; i++) {
// For the rest of elements
// taking the max of
// operations already done +
// the ones performed here
max_operations
= Math.max(
max_operations,
Math.abs(arr[i] - arr[i - 1])
+ Math.abs(arr[i + 1] - arr[i])
- Math.abs(arr[i + 1] - arr[i - 1]));
}
// Print the final result
document.write((result - max_operations) + "</br>");
}
// Driver Code
let N = 3;
let arr = [-1, 0, 2];
findMinOperations(arr, N);
// This code is contributed by Potta Lokesh
</script>
Producción
1
Complejidad temporal : O(N)
Espacio auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por singhh3010 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA