Programa C++ para el índice de equilibrio de una array

El índice de equilibrio de una array es un índice tal que la suma de los elementos en los índices más bajos es igual a la suma de los elementos en los índices más altos. Por ejemplo, en una array A: 

Ejemplo : 

Entrada : A[] = {-7, 1, 5, 2, -4, 3, 0} 
Salida : 3 
3 es un índice de equilibrio, porque: 
A[0] + A[1] + A[2] = A [4] + A[5] + A[6]

Entrada : A[] = {1, 2, 3} 
Salida : -1 

Escribe una función int equilibrio(int[] arr, int n) ; que dada una secuencia arr[] de tamaño n, devuelve un índice de equilibrio (si lo hay) o -1 si no existen índices de equilibrio. 

Método 1 (Simple pero ineficiente) 
Use dos bucles. El bucle externo itera a través de todo el elemento y el bucle interno descubre si el índice actual elegido por el bucle externo es un índice de equilibrio o no. La complejidad temporal de esta solución es O(n^2). 

// C++ program to find equilibrium
// index of an array
#include <bits/stdc++.h>
using namespace std;
  
int equilibrium(int arr[], int n)
{
    int i, j;
    int leftsum, rightsum;
  
    /* Check for indexes one by one until 
    an equilibrium index is found */
    for (i = 0; i < n; ++i) 
    {     
  
        /* get left sum */
        leftsum = 0; 
        for (j = 0; j < i; j++)
            leftsum += arr[j];
  
        /* get right sum */
        rightsum = 0; 
        for (j = i + 1; j < n; j++)
            rightsum += arr[j];
  
        /* if leftsum and rightsum  
        are same, then we are done */
        if (leftsum == rightsum)
            return i;
    }
  
    /* return -1 if no equilibrium 
    index is found */
    return -1;
}
  
// Driver code
int main()
{
    int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    cout << equilibrium(arr, arr_size);
    return 0;
}
  
// This code is contributed 
// by Akanksha Rai(Abby_akku)

3

Complejidad del tiempo: O(n^2)

Método 2 (complicado y eficiente) 
La idea es obtener primero la suma total de la array. Luego itere a través de la array y siga actualizando la suma izquierda que se inicializa como cero. En el ciclo, podemos obtener la suma correcta restando los elementos uno por uno. Gracias a Sambasiva por sugerir esta solución y proporcionar el código para esto.

1) Initialize leftsum  as 0
2) Get the total sum of the array as sum
3) Iterate through the array and for each index i, do following.
    a)  Update sum to get the right sum.  
           sum = sum - arr[i] 
       // sum is now right sum
    b) If leftsum is equal to sum, then return current index. 
       // update leftsum for next iteration.
    c) leftsum = leftsum + arr[i]
4) return -1 
// If we come out of loop without returning then
// there is no equilibrium index

La siguiente imagen muestra la ejecución en seco del enfoque anterior: 

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to find equilibrium 
// index of an array 
#include <bits/stdc++.h>
using namespace std;
  
int equilibrium(int arr[], int n) 
{ 
    int sum = 0; // initialize sum of whole array 
    int leftsum = 0; // initialize leftsum 
  
    /* Find sum of the whole array */
    for (int i = 0; i < n; ++i) 
        sum += arr[i]; 
  
    for (int i = 0; i < n; ++i) 
    { 
        sum -= arr[i]; // sum is now right sum for index i 
  
        if (leftsum == sum) 
            return i; 
  
        leftsum += arr[i]; 
    } 
  
    /* If no equilibrium index found, then return 0 */
    return -1; 
} 
  
// Driver code 
int main() 
{ 
    int arr[] = { -7, 1, 5, 2, -4, 3, 0 }; 
    int arr_size = sizeof(arr) / sizeof(arr[0]); 
    cout << "First equilibrium index is " << equilibrium(arr, arr_size); 
    return 0; 
} 
  
// This is code is contributed by rathbhupendra

First equilibrium index is 3

Salida: El 
primer índice de equilibrio es 3

Complejidad de tiempo: O(n)

Método 3:

Este es un método bastante simple y directo. La idea es tomar la suma del prefijo de la array dos veces. Una vez desde el extremo frontal de la array y otra desde la parte posterior de la array.

Después de tomar ambas sumas de prefijos, ejecute un ciclo y verifique si hay alguna i si la suma de prefijos de una array es igual a la suma de prefijos de la segunda array, entonces ese punto puede considerarse como el punto de equilibrio.

// C++ program to find equilibrium index of an array
#include <bits/stdc++.h>
using namespace std;
  
int equilibrium(int a[], int n)
{
    if (n == 1)
        return (0);
    int forward[n] = { 0 };
    int rev[n] = { 0 };
  
    // Taking the prefixsum from front end array
    for (int i = 0; i < n; i++) {
        if (i) {
            forward[i] = forward[i - 1] + a[i];
        }
        else {
            forward[i] = a[i];
        }
    }
  
    // Taking the prefixsum from back end of array
    for (int i = n - 1; i > 0; i--) {
        if (i <= n - 2) {
            rev[i] = rev[i + 1] + a[i];
        }
        else {
            rev[i] = a[i];
        }
    }
  
    // Checking if forward prefix sum
    // is equal to rev prefix
    // sum
    for (int i = 0; i < n; i++) {
        if (forward[i] == rev[i]) {
            return i;
        }
    }
    return -1;
  
    // If You want all the points
    // of equilibrium create
    // vector and push all equilibrium
    // points in it and
    // return the vector
}
  
// Driver code
int main()
{
    int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "First Point of equilibrium is at index "
         << equilibrium(arr, n) << "
";
    return 0;
}

First Point of equilibrium is at index 3

Complejidad de tiempo: O(N)

Complejidad espacial: O(N)

Consulte el artículo completo sobre el índice de equilibrio de una array para obtener más detalles.