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 <stdio.h>
  
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]);
    printf("%d", equilibrium(arr, arr_size));
  
    getchar();
    return 0;
}

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 <stdio.h>
  
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]);
    printf("First equilibrium index is %d", 
                 equilibrium(arr, arr_size));
  
    getchar();
    return 0;
}

First equilibrium index is 3

Salida: El 
primer índice de equilibrio es 3

Complejidad de tiempo: O(n)

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