Dada una array arr[] de N elementos y un entero X , la tarea es encontrar el número mínimo de operaciones requeridas para hacer que la suma de los elementos vecinos sea menor que el número dado X. En una sola operación, puede elegir un elemento arr[i] y disminuir su valor en 1 .
Ejemplos:
Entrada: arr[] = {2, 2, 2}, X = 3
Salida: 1
Decremente arr[1] en 1 y la array se convierte en {2, 1, 2}.
Ahora, 2 + 1 = 3 y 1 + 2 = 3
Entrada: arr[] = {1, 6, 1, 2, 0, 4}, X = 1
Salida: 11
Enfoque: suponga que los elementos de la array son a1, a2, …, an . Supongamos un caso en el que todos los a[i] son mayores que X.
Primero necesitamos hacer que todos los a[i] sean iguales a x . Calcularemos el número de operaciones necesarias para ello.
Ahora, todos los elementos tendrán la forma de x, x, x, x…, x N veces. Aquí podemos observar que la suma vecina máxima es igual a 2 * X .
Ahora, recorra la array de izquierda a derecha, y para cada i , si la suma de dos vecinos a la izquierda es a[i] + a[i – 1] > X , entonces cambie a[i]a un valor tal que su suma neta sea igual a X .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum
// number of operations required
int MinOperations(int n, int x, int* arr)
{
// To store total operations required
int total = 0;
for (int i = 0; i < n; ++i) {
// First make all elements equal to x
// which are currenctly greater
if (arr[i] > x) {
int difference = arr[i] - x;
total = total + difference;
arr[i] = x;
}
}
// Left scan the array
for (int i = 1; i < n; ++i) {
int LeftNeigbouringSum = arr[i] + arr[i - 1];
// Update the current element such that
// neighbouring sum is < x
if (LeftNeigbouringSum > x) {
int current_diff = LeftNeigbouringSum - x;
arr[i] = max(0, arr[i] - current_diff);
total = total + current_diff;
}
}
return total;
}
// Driver code
int main()
{
int X = 1;
int arr[] = { 1, 6, 1, 2, 0, 4 };
int N = sizeof(arr) / sizeof(int);
cout << MinOperations(N, X, arr);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the minimum
// number of operations required
static int MinOperations(int n, int x, int[] arr)
{
// To store total operations required
int total = 0;
for (int i = 0; i < n; ++i)
{
// First make all elements equal to x
// which are currenctly greater
if (arr[i] > x)
{
int difference = arr[i] - x;
total = total + difference;
arr[i] = x;
}
}
// Left scan the array
for (int i = 1; i < n; ++i)
{
int LeftNeigbouringSum = arr[i] + arr[i - 1];
// Update the current element such that
// neighbouring sum is < x
if (LeftNeigbouringSum > x)
{
int current_diff = LeftNeigbouringSum - x;
arr[i] = Math.max(0, arr[i] - current_diff);
total = total + current_diff;
}
}
return total;
}
// Driver code
public static void main(String args[])
{
int X = 1;
int arr[] = { 1, 6, 1, 2, 0, 4 };
int N = arr.length;
System.out.println(MinOperations(N, X, arr));
}
}
// This code is contributed by 29AjayKumar
Python
# Python3 implementation of the approach # Function to return the minimum # number of operations required def MinOperations(n, x, arr): # To store total operations required total = 0 for i in range(n): # First make all elements equal to x # which are currenctly greater if (arr[i] > x): difference = arr[i] - x total = total + difference arr[i] = x # Left scan the array for i in range(n): LeftNeigbouringSum = arr[i] + arr[i - 1] # Update the current element such that # neighbouring sum is < x if (LeftNeigbouringSum > x): current_diff = LeftNeigbouringSum - x arr[i] = max(0, arr[i] - current_diff) total = total + current_diff return total # Driver code X = 1 arr=[1, 6, 1, 2, 0, 4 ] N = len(arr) print(MinOperations(N, X, arr)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the minimum
// number of operations required
static int MinOperations(int n, int x, int[] arr)
{
// To store total operations required
int total = 0;
for (int i = 0; i < n; ++i)
{
// First make all elements equal to x
// which are currenctly greater
if (arr[i] > x)
{
int difference = arr[i] - x;
total = total + difference;
arr[i] = x;
}
}
// Left scan the array
for (int i = 1; i < n; ++i)
{
int LeftNeigbouringSum = arr[i] + arr[i - 1];
// Update the current element such that
// neighbouring sum is < x
if (LeftNeigbouringSum > x)
{
int current_diff = LeftNeigbouringSum - x;
arr[i] = Math.Max(0, arr[i] - current_diff);
total = total + current_diff;
}
}
return total;
}
// Driver code
public static void Main(String []args)
{
int X = 1;
int []arr = { 1, 6, 1, 2, 0, 4 };
int N = arr.Length;
Console.WriteLine(MinOperations(N, X, arr));
}
}
/* This code is contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum
// number of operations required
function MinOperations(n, x, arr)
{
// To store total operations required
let total = 0;
for (let i = 0; i < n; ++i)
{
// First make all elements equal to x
// which are currenctly greater
if (arr[i] > x)
{
let difference = arr[i] - x;
total = total + difference;
arr[i] = x;
}
}
// Left scan the array
for (let i = 1; i < n; ++i)
{
let LeftNeigbouringSum = arr[i] + arr[i - 1];
// Update the current element such that
// neighbouring sum is < x
if (LeftNeigbouringSum > x)
{
let current_diff = LeftNeigbouringSum - x;
arr[i] = Math.max(0, arr[i] - current_diff);
total = total + current_diff;
}
}
return total;
}
// Driver code
let X = 1;
let arr = [ 1, 6, 1, 2, 0, 4 ];
let N = arr.length;
document.write(MinOperations(N, X, arr)+"<br>");
// This code is contributed by rag2127
</script>
Producción:
11