Dada una array A[] de longitud N, la tarea es encontrar el número entero mínimo que se agregará en cualquier extremo de la array para que esté en equilibrio.
Un arreglo está en equilibrio si existe algún índice i tal que:
suma de A[0, . . ., i-1] = suma de A[i+1, . . ., N-1]
Ejemplo:
Entrada: A[] = {5, 2, 6, 4, 3, 2}
Salida: 2
Explicación: En la array anterior, el entero 2 se agrega al frente de la array, luego la array se convierte en {2, 5, 2, 6, 4, 3, 2}.
Por lo tanto, el índice 3 es nuestro punto de equilibrio.Entrada: A[] = {0, 6, 3, 4, 9}
Salida: 0
Enfoque: el problema se puede resolver utilizando el enfoque de dos punteros como se menciona a continuación:
- Mantenga el puntero izquierdo al principio y el puntero derecho al final de la array
- Iterar los siguientes pasos hasta que el puntero izquierdo y derecho se vuelvan adyacentes:
- Si la suma de la array desde el puntero inicial hasta el izquierdo (= suma_izquierda) es al menos la suma de la array desde el puntero derecho hasta el final (= suma_derecha), disminuya el puntero derecho en 1
- de lo contrario, incremente el puntero izquierdo en 1
- Al final, la diferencia absoluta entre la suma de la derecha y la suma de la izquierda será el número mínimo requerido que se agregará en el dado para que la array permanezca en equilibrio,
Ilustración:
Considere: A[] = {5, 2, 6, 4, 3, 2}
Inicialmente, el puntero izquierdo apuntará al elemento 5 y el puntero derecho apuntará al elemento 2
- Dado que right_pointer no es adyacente a left_pointer, Iteración 1 :
- suma_izquierda = 5 y suma_derecha = 2,
- ya que left_sum ≥ right_sum, por lo tanto, desplazar right_pointer a 1 izquierda (ahora en el elemento 3)
- Dado que right_pointer no es adyacente a left_pointer, Iteración 2 :
- suma_izquierda = 5 y suma_derecha = 5,
- ya que left_sum = right_sum, por lo tanto, cambie el puntero_derecho a 1 a la izquierda (ahora en el elemento 4) y el puntero_izquierdo a 1 a la derecha (ahora en el elemento 2)
- Dado que right_pointer no es adyacente a left_pointer, Iteración 3 :
- suma_izquierda = 7 y suma_derecha = 9,
- ya que left_sum < right_sum, por lo tanto, cambie el puntero izquierdo a 1 (ahora en el elemento 6)
- Aquí en la iteración 4 , dado que right_pointer está adyacente a left_pointer, rompa el ciclo y vaya al siguiente paso
- Encuentra la diferencia absoluta entre left_sum y right_sum = abs(9 – 7) = 2
Por lo tanto, 2 es el número mínimo que debe agregarse a la array para que permanezca en equilibrio.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of above approach.
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum integer
// to be added either in front or at end
// of the array to make it equilibrium
int makeEquilibrium(int arr[], int n)
{
int i = 1, j = n - 2;
// Initialize left and right sum with
// first and last value of array
int leftSum = arr[0], rightSum = arr[n - 1];
while (i <= j) {
// If there is only one element present
// between i and j, return
// absolute value of left and right sum
// which generate ans
if (j - i < 1)
return abs(leftSum - rightSum);
// If left sum is less
// increment i and add
// element from front
if (leftSum < rightSum) {
leftSum += arr[i++];
}
// If right sum is less
// decrement j and add
// element from end
else if (leftSum > rightSum) {
rightSum += arr[j--];
}
// when both sum become equal
else {
leftSum += arr[i++];
rightSum += arr[j--];
}
}
}
// Driver code
int main()
{
int arr[] = { 5, 2, 6, 4, 3, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << makeEquilibrium(arr, N);
return 0;
}
Java
// JAVA program of above approach.
import java.util.*;
class GFG
{
// Function to find minimum integer
// to be added either in front or at end
// of the array to make it equilibrium
public static int makeEquilibrium(int arr[], int n)
{
int i = 1, j = n - 2;
// Initialize left and right sum with
// first and last value of array
int leftSum = arr[0], rightSum = arr[n - 1];
while (i <= j) {
// If there is only one element present
// between i and j, return
// absolute value of left and right sum
// which generate ans
if (j - i < 1)
return Math.abs(leftSum - rightSum);
// If left sum is less
// increment i and add
// element from front
if (leftSum < rightSum) {
leftSum += arr[i++];
}
// If right sum is less
// decrement j and add
// element from end
else if (leftSum > rightSum) {
rightSum += arr[j--];
}
// when both sum become equal
else {
leftSum += arr[i++];
rightSum += arr[j--];
}
}
return 0;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 5, 2, 6, 4, 3, 2 };
int N = arr.length;
System.out.print(makeEquilibrium(arr, N));
}
}
// This code is contributed by Taranpreet
Python3
# python3 program of above approach. # Function to find minimum integer # to be added either in front or at end # of the array to make it equilibrium def makeEquilibrium(arr, n): i, j = 1, n - 2 # left and right sum with # first and last value of array leftSum, rightSum = arr[0], arr[n - 1] while (i <= j): # If there is only one element present # between i and j, return # absolute value of left and right sum # which generate ans if (j - i < 1): return abs(leftSum - rightSum) # If left sum is less # increment i and add # element from front if (leftSum < rightSum): leftSum += arr[i] i += 1 # If right sum is less # decrement j and add # element from end elif (leftSum > rightSum): rightSum += arr[j] j -= 1 # when both sum become equal else: leftSum += arr[i] i += 1 rightSum += arr[j] j -= 1 # Driver code if __name__ == "__main__": arr = [5, 2, 6, 4, 3, 2] N = len(arr) print(makeEquilibrium(arr, N)) # This code is contributed by rakeshsahni
C#
// C# program of above approach.
using System;
public class GFG{
// Function to find minimum integer
// to be added either in front or at end
// of the array to make it equilibrium
static int makeEquilibrium(int[] arr, int n)
{
int i = 1, j = n - 2;
// Initialize left and right sum with
// first and last value of array
int leftSum = arr[0], rightSum = arr[n - 1];
while (i <= j) {
// If there is only one element present
// between i and j, return
// absolute value of left and right sum
// which generate ans
if (j - i < 1)
return Math.Abs(leftSum - rightSum);
// If left sum is less
// increment i and add
// element from front
if (leftSum < rightSum) {
leftSum += arr[i++];
}
// If right sum is less
// decrement j and add
// element from end
else if (leftSum > rightSum) {
rightSum += arr[j--];
}
// when both sum become equal
else {
leftSum += arr[i++];
rightSum += arr[j--];
}
}
return 0;
}
// Driver code
static public void Main ()
{
int[] arr = { 5, 2, 6, 4, 3, 2 };
int N = arr.Length;
Console.Write(makeEquilibrium(arr, N));
}
}
// This code is contributed by hrithikgarg03188.
Javascript
<script>
// JavaScript program of above approach.
// Function to find minimum integer
// to be added either in front or at end
// of the array to make it equilibrium
const makeEquilibrium = (arr, n) => {
let i = 1, j = n - 2;
// Initialize left and right sum with
// first and last value of array
let leftSum = arr[0], rightSum = arr[n - 1];
while (i <= j) {
// If there is only one element present
// between i and j, return
// absolute value of left and right sum
// which generate ans
if (j - i < 1)
return Math.abs(leftSum - rightSum);
// If left sum is less
// increment i and add
// element from front
if (leftSum < rightSum) {
leftSum += arr[i++];
}
// If right sum is less
// decrement j and add
// element from end
else if (leftSum > rightSum) {
rightSum += arr[j--];
}
// when both sum become equal
else {
leftSum += arr[i++];
rightSum += arr[j--];
}
}
}
// Driver code
let arr = [5, 2, 6, 4, 3, 2];
let N = arr.length;
document.write(makeEquilibrium(arr, N));
// This code is contributed by rakeshsahni
</script>
Producción
2
Complejidad Temporal: O(N)
Espacio Auxiliar: O(1).