Finding equilibrium index of an array in C

Finding equilibrium index of an array in C

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[ ] : [-4, 3, 0, 2, -7, 1, 5], in the given array index 3 is an euqilibrium index as  left_sum =  right_sum = -1.   

equilibrium index of an array in C programming
equilibrium index of an array in C programming

Algorithm :

  • Take the size of array from the user, and store it in n.
  • Take the n elements of the array from the user.
  • Initialize left_sum, and find the sum of the elements of array and store it in sum .
  • Iterate from 1 to n-1 and for every i-th index update, left_sum += a[i] and sum -= a[i].
  • Check if left_sum == sum , then that index is the required equilibrium index.

Method -1 C Program based on above algorithm

#include<iostream>
int main ()
{
int n;

printf ("Enter the size of the array: ");
scanf ("%d", &n);

int a[n], sum = 0, left_sum = 0;
printf ("\nEnter the elements of the array: ");
for (int i = 0; i < n; i++)
{
scanf ("%d", &a[i]);
sum += a[i];
}
left_sum = a[0];
sum -= a[0];
for (int i = 1; i < n; i++)
{
sum -= a[i];
if (left_sum == sum)
{
printf ("\nEquilibrim index : %d", i);
break;
}
left_sum += a[i];
}
return 0;
}

Output

(Test case 1)

Enter the size of the array: 5

Enter the elements of the array: 1
2
0
1
2

(Test case 2)

Equilibrim index : 2

Enter the size of the array: 7

Enter the elements of the array: 1
2
3
0
1
2
3

Equilibrim index : 3

Method -2 

Use two loops. Outer loop iterates through all the element and inner loop finds out whether the current index picked by the outer loop is equilibrium index or not. Time complexity of this solution is O(n^2). 


#include <stdio.h>

using namespace std;
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)
{
cout << "First Point of equilibrium is at index =" << mid << endl;
return;
}

cout << "First Point of equilibrium is at index =" << -1 << endl;
}

int main ()
{
int arr[100], n;
printf ("Enter size of array= ");
scanf ("%d", &n);
printf ("Enter element of array= ");
for (int i = 0; i < n; i++)
{
scanf ("%d", &arr[i]);
}

find (arr, n);
}

Output

Enter size of array= 5
Enter element of array= 1
2
3
4
5
Answer = -1
Enter size of array= 7
Enter element of array= 1
1
1
-1
1
1
1
Answer = 2

Method -3 (Binary search)

  • 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
#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)
{
cout << "First Point of equilibrium is at index =" << mid << endl;
return;
}

cout << "First Point of equilibrium is at index =" << -1 << endl;
}

int main ()
{
int arr[100], n;
printf ("Enter size of array= ");
scanf ("%d", &n);
printf ("Enter element of array= ");
for (int i = 0; i < n; i++)
{
scanf ("%d", &arr[i]);
}

find (arr, n);
return 0;
}

Output

Enter size of array= 7
Enter element of array= 1
2
1
-1
1
2
1
First Point of equilibrium is at index =3