Finding equilibrium index of an array in C

February 18, 2022

Finding equilibrium index of an array

Here, in this section we will learn about Finding equilibrium index of an array in C program. 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.

Example

arr[7] : [-4, 3, 0, 2, -7, 1, 5],
Index 3 is an euqilibrium index as left_sum = right_sum = -1.
left_sum = -4+3+0 = -1
right_sum = -7+1+5 = -1

Here, we will discuss the following two methods,

Method 1 : Using Nested loops.
Method 2 : Using single for loop
Method 3 : Using Binary search concept.

Method 1 :

Run a loop from index 0 to n.
Create a variable say left_sum =0, to find the left indexed value sum.
Run a loop from index 0 to i to find left_sum.
Similarly, declare right_sum = 0,
Run a loop from index i to n, and find right_sum.
If left_sum == right_sum, return i.

Method 1 : Code in C

#include<stdio.h>

void find (int arr[], int n)
{
  int result = -1;
  
  for(int i=0; i<n; i++){
    
    int left_sum =0;
    for(int j=0; j<i; j++)
       left_sum += arr[i];
    int right_sum =0;
    for(int j=i+1; j<n; j++)
       right_sum += arr[i];
    
    if(right_sum == left_sum)
    result = i;
      
  }
  
    printf("First Point of equilibrium is at index = %d\n", result);
    return;
  
}

int main ()
{
  int arr[]={4, -2, 0, 6, -4};
  int n = sizeof(arr)/sizeof(arr[0]);

  find (arr, n);
  return 0;
}

Output

Equilibrium index : 3

Method 2 :

In this method we will use single loop to find the equilibrium point in the array.

Method 2 : Code in C

#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]; 
 
        if (leftsum == sum)
            return i;
 
        leftsum += arr[i];
    }
 
    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;
}

Output

Equilibrium index : 3

Method 3 :

To handle all the testcase, we can use binary search algorithm.
Calculate the mid and then create left sum and right sum around mid
if left sum is greater than right sum, move to left until it become equal or less than right sum
else if right sum is greater than left, move right until it become equal or less than left sum.
finally we compare two sums if they are equal we got mid as index else its -1

Method 3 : Code in C

#include<stdio.h>

void find (int arr[], int n)
{
  int mid = n / 2;
  int leftSum = 0, rightSum = 0;

  //calculation sum to left of mid
  for (int i = 0; i < mid; i++){ leftSum += arr[i]; } //calculating sum to right of mid
    for (int i = n - 1; i > mid; i--){
    rightSum += arr[i];
  }

  //if rightsum > leftsum
  if (rightSum > leftSum){
    //we keep moving right until rightSum become equal or less than leftSum
    while (rightSum > leftSum && mid < n - 1){ 
        rightSum -= arr[mid + 1]; 
        leftSum += arr[mid]; 
        mid++;
    } 
  } 
  else{ //we keep moving right until leftSum become equal or less than RightSum 
      while (leftSum > rightSum && mid > 0){
	rightSum += arr[mid];
	leftSum -= arr[mid - 1];
	mid--;
    }
  }

  //check if both sum become equal
  if (rightSum == leftSum){
    printf("First Point of equilibrium is at index = %d\n", mid);
    return;
  }

  printf("First Point of equilibrium is at index = -1 ");
}

int main ()
{
  int arr[]={4, -2, 0, 6, -4};
  int n = sizeof(arr)/sizeof(arr[0]);

  find (arr, n);
  return 0;
}

Output

First Point of equilibrium is at index = 2