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 <iostream>
using namespace std;

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) {
            cout << "Equilibrium Index: " << i << endl;
        }
    }
}

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 <iostream>
using namespace std;

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) {
            cout << "Equilibrium Index: " << i << endl;
        }
        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 <iostream>
using namespace std;

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) cout << "Equilibrium Index: " << eqIndex << endl;
}

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