Finding Equilibrium Index of an Array in C

Understanding Equilibrium Index

The equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.

We will explore three different methods to solve this problem in C.

Method 1: Using Brute Force

#include <stdio.h>

void findEquilibrium(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        int leftSum = 0, rightSum = 0;
        for (int j = 0; j < i; j++) leftSum += arr[j];
        for (int j = i + 1; j < n; j++) rightSum += arr[j];
        if (leftSum == rightSum) {
            printf("Equilibrium Index: %d\n", i);
        }
    }
}

int main() {
    int arr[] = {-7, 1, 5, 2, -4, 3, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    findEquilibrium(arr, n);
    return 0;
}
            

Output:

Equilibrium Index: 3
Equilibrium Index: 6
            

Method 2: Using Prefix Sum

#include <stdio.h>

void findEquilibrium(int arr[], int n) {
    int totalSum = 0, leftSum = 0;
    for (int i = 0; i < n; i++) totalSum += arr[i];
    for (int i = 0; i < n; i++) {
        totalSum -= arr[i];
        if (leftSum == totalSum) {
            printf("Equilibrium Index: %d\n", i);
        }
        leftSum += arr[i];
    }
}

int main() {
    int arr[] = {-7, 1, 5, 2, -4, 3, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    findEquilibrium(arr, n);
    return 0;
}
            

Output:

Equilibrium Index: 3
Equilibrium Index: 6
            

Method 3: Using Recursion

#include <stdio.h>

int equilibriumHelper(int arr[], int n, int index, int leftSum, int totalSum) {
    if (index == n) return -1;
    totalSum -= arr[index];
    if (leftSum == totalSum) return index;
    return equilibriumHelper(arr, n, index + 1, leftSum + arr[index], totalSum);
}

void findEquilibrium(int arr[], int n) {
    int totalSum = 0;
    for (int i = 0; i < n; i++) totalSum += arr[i];
    int eqIndex = equilibriumHelper(arr, n, 0, 0, totalSum);
    if (eqIndex != -1) printf("Equilibrium Index: %d\n", eqIndex);
}

int main() {
    int arr[] = {-7, 1, 5, 2, -4, 3, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    findEquilibrium(arr, n);
    return 0;
}
            

Output:

Equilibrium Index: 3