Equilibrium Index of an Array in C

Introduction to Equilibrium Index

The equilibrium index of an array is an index such that the sum of elements at lower indices is equal to the sum of elements at higher indices. In other words, for an array arr[] of size n, an index i is an equilibrium index if:

Key points about equilibrium index:

• First and last positions: Index 0 is an equilibrium index if sum of all elements except first is 0. Index n-1 is an equilibrium index if sum of all elements except last is 0.
• Multiple equilibrium indices: An array can have multiple equilibrium indices.
• No equilibrium index: Some arrays may not have any equilibrium index.
• Important concept: Used in various problems like prefix sum, subarray sum, and pivot index problems.

C Program to Find Equilibrium Index

#include <stdio.h>

// Function to find equilibrium index using total sum approach
int equilibriumIndex(int arr[], int n) {
    int totalSum = 0;
    
    // Calculate total sum of the array
    for (int i = 0; i < n; i++) {
        totalSum += arr[i];
    }
    
    int leftSum = 0;
    
    // Traverse the array from left to right
    for (int i = 0; i < n; i++) {
        // Remove current element from total sum to get right sum
        int rightSum = totalSum - leftSum - arr[i];
        
        // Check if left sum equals right sum
        if (leftSum == rightSum) {
            return i; // Found equilibrium index
        }
        
        // Update left sum for next iteration
        leftSum += arr[i];
    }
    
    return -1; // No equilibrium index found
}

// Function to find all equilibrium indices
void findAllEquilibriumIndices(int arr[], int n) {
    int totalSum = 0;
    
    for (int i = 0; i < n; i++) {
        totalSum += arr[i];
    }
    
    int leftSum = 0;
    int found = 0;
    
    printf("Equilibrium indices: ");
    for (int i = 0; i < n; i++) {
        int rightSum = totalSum - leftSum - arr[i];
        
        if (leftSum == rightSum) {
            printf("%d ", i);
            found = 1;
        }
        
        leftSum += arr[i];
    }
    
    if (!found) {
        printf("None");
    }
    printf("\n");
}

// Function to print the array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Driver program to test the equilibrium index
int main() {
    int arr1[] = {-7, 1, 5, 2, -4, 3, 0};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    
    printf("Array 1: ");
    printArray(arr1, n1);
    
    int eqIndex1 = equilibriumIndex(arr1, n1);
    if (eqIndex1 != -1) {
        printf("Equilibrium index: %d\n", eqIndex1);
        printf("Left sum: ");
        for (int i = 0; i < eqIndex1; i++) {
            printf("%d ", arr1[i]);
        }
        printf("= %d\n", eqIndex1);
        printf("Right sum: ");
        for (int i = eqIndex1 + 1; i < n1; i++) {
            printf("%d ", arr1[i]);
        }
        printf("= %d\n", eqIndex1);
    } else {
        printf("No equilibrium index found.\n");
    }
    
    printf("\n");
    
    int arr2[] = {1, 2, 3, 4, 5, 6};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    
    printf("Array 2: ");
    printArray(arr2, n2);
    findAllEquilibriumIndices(arr2, n2);
    
    printf("\n");
    
    int arr3[] = {0, 0, 0, 0};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    
    printf("Array 3: ");
    printArray(arr3, n3);
    findAllEquilibriumIndices(arr3, n3);
    
    return 0;
}

Sample Output

Array 1: -7 1 5 2 -4 3 0 
Equilibrium index: 3
Left sum: -7 1 5 = -1
Right sum: -4 3 0 = -1

Array 2: 1 2 3 4 5 6 
Equilibrium indices: None

Array 3: 0 0 0 0 
Equilibrium indices: 0 1 2 3

Another Example:

Array: 1 3 5 2 2 
Equilibrium index: 2
Left sum: 1 + 3 = 4
Right sum: 2 + 2 = 4

Program Explanation

Let's break down the code step by step:

1. Include Header File: #include <stdio.h> includes the standard input/output library.
2. Equilibrium Index Function:
   • Step 1: Calculate total sum of the array using a loop
   • Step 2: Initialize leftSum = 0
   • Step 3: Traverse the array from left to right:
     • Calculate rightSum = totalSum - leftSum - arr[i]
     • If leftSum == rightSum, return i
     • Add current element to leftSum
   • Step 4: Return -1 if no equilibrium index is found
3. Find All Equilibrium Indices Function:
   • Uses the same approach but stores and prints all indices
   • Useful when multiple equilibrium indices exist
4. Print Function: Displays all elements of the array.
5. Main Function:
   • Tests the algorithm on different arrays
   • Demonstrates both single and multiple equilibrium index scenarios
   • Displays left and right sums for verification

Step-by-Step Approach

Algorithm for Equilibrium Index

1. Calculate Total Sum:
   • totalSum = sum(arr[0] to arr[n-1])
2. Initialize:
   • leftSum = 0
3. Traverse:
   • For i = 0 to n-1:
     • rightSum = totalSum - leftSum - arr[i]
     • If leftSum == rightSum: return i
     • leftSum += arr[i]
4. Return: Return -1 if no equilibrium index is found

Time & Space Complexity

// Using prefix sum array
int equilibriumIndexPrefix(int arr[], int n) {
    int prefixSum[n];
    int totalSum = 0;
    
    // Build prefix sum array
    for (int i = 0; i < n; i++) {
        totalSum += arr[i];
        prefixSum[i] = totalSum;
    }
    
    for (int i = 0; i < n; i++) {
        int leftSum = (i == 0) ? 0 : prefixSum[i - 1];
        int rightSum = totalSum - prefixSum[i];
        
        if (leftSum == rightSum) {
            return i;
        }
    }
    return -1;
}

// For floating point numbers
int equilibriumIndexFloat(float arr[], int n) {
    float totalSum = 0.0;
    for (int i = 0; i < n; i++) {
        totalSum += arr[i];
    }
    
    float leftSum = 0.0;
    for (int i = 0; i < n; i++) {
        float rightSum = totalSum - leftSum - arr[i];
        if (leftSum == rightSum) {
            return i;
        }
        leftSum += arr[i];
    }
    return -1;
}

Frequently Asked Questions

Previous Topic: -->> Counting Sort in C   ||   Next topic: -->> Prefix Sum Array in C