Find the equilibrium index of an array | faceprep

Program to find the equilibrium index of an array is discussed here. Equilibrium index of an array is an index such that 

Sum of elements at lower indexes = Sum of elements at higher indexes.

For example, consider the array a[] = {-7, 1, 5, 2, -4, 3, 0}. Here, a[0] + a[1] + a[2] = a[4] + a[5] + a[6]. Hence, 3 is the equilibrium index.

Method 1:

  • Using two loops.
  • Outer loop iterates through all the element and the inner loop check out whether the current index picked by the outer loop is either equilibrium index or not.
  • The time complexity of this solution is O(n^2).

equilibrium index of an array

Program to find the equilibrium index of an array

// C program to find the equilibrium index of an array

#include

int equilibrium_index(int arr[], int n)
{
int i, j;
int leftsum, rightsum;

for (i = 0; i < n; ++i) {

leftsum = 0;
for (j = 0; j < i; j++)
leftsum += arr[j];

rightsum = 0;
for (j = i + 1; j < n; j++)
rightsum += arr[j];

if (leftsum == rightsum)
return i;
}

return -1;
}

int main()
{
int n;
printf(“\nEnter the number of elements : “);
scanf(“%d”,&n);
int arr[n];
printf(“\nInput the array elements : “);
for(int i = 0; i < n; i++)
{
scanf(“%d”,&arr[i]);
}
printf(“\nEquilibrium Index : %d\n”, equilibrium_index(arr, n));
return 0;
}

// C++ program to find the equilibrium index of an array

#include <iostream>
using namespace std;

int equilibrium_index(int arr[], int n)
{
int i, j;
int leftsum, rightsum;

for (i = 0; i < n; ++i)
{
leftsum = 0;
for (j = 0; j < i; j++)
leftsum += arr[j];

rightsum = 0;
for (j = i + 1; j < n; j++)
rightsum += arr[j];

if (leftsum == rightsum)
return i;
}

return -1;
}

int main()
{
int n;
cout <<“\nEnter the number of elements : “;
cin >> n;
int arr[n];
cout <<“\nInput the array elements : “;
for(int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout <<“\nEquilibrium Index : ” << equilibrium_index(arr, n) << endl;
return 0;
}

// Java program to find the equilibrium index of an array

public class Main
{
static int equilibrium_index(int arr[], int n)
{
int i, j;
int leftsum, rightsum;


for (i = 0; i < n; ++i) {

leftsum = 0;
for (j = 0; j < i; j++)
leftsum += arr[j];

rightsum = 0;
for (j = i + 1; j < n; j++)
rightsum += arr[j];


if (leftsum == rightsum)
return i;
}

return -1;
}

public static void main(String[] args)
{
int arr[] = { 1,2,3,4,5,1,3,2,4 };
int arr_size = arr.length;
System.out.print(“Equilibrium Index : “);
System.out.println(equilibrium_index(arr, arr_size));
}
}

# Python program to find the equilibrium index of an array

def equilibrium_index(arr):
leftsum = 0
rightsum = 0
n = len(arr)

for i in range(n):
leftsum = 0
rightsum = 0
for j in range(i):
leftsum += arr[j]

for j in range(i + 1, n):
rightsum += arr[j]

if leftsum == rightsum:
return i

return -1

arr = [1,2,3,4,5,1,2,3,4]
print(“Equilibrium Index : “, end = “”)
print (equilibrium_index(arr))

 

Time complexity: O(n^2)

Method 2:

Find the sum of the array and then traverse through the array and keep updating the leftsum which is initially zero. To get the right sum, subtract the array values from the sum while traversing. Check left sum and right sum at each step. If they are equal, return the current index.

Algorithm:

  • Initialize left_sum = 0
  • Find the sum of the array as sum.
  • For i = 1 to end of the array, do the following:
  1. Update sum to get the right sum.
  2. sum = sum – arr[i]  // sum is the right sum.
  3. If left_sum == sum, return current index.
  4. Update left_sum = left_sum + arr[i]
  • Return -1 and exit the algorithm. // Equilibrium index is not found.

Program to find the equilibrium index of an array

#include <stdio.h>

int equilibrium_index(int arr[], int n)
{
int sum = 0;
int leftsum = 0;

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;
}

int main()
{
int n;
printf(“\nEnter the number of elements : “);
scanf(“%d”,&n);
int arr[n];
printf(“\nInput the array elements : “);
for(int i = 0; i < n; i++)
{
scanf(“%d”,&arr[i]);
}
printf(“\nEquilibrium Index : %d\n”, equilibrium_index(arr, n));
return 0;
}

#include <iostream>
using namespace std;

int equilibrium_index(int arr[], int n)
{
int sum = 0;
int leftsum = 0;

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;
}

int main()
{
int n;
cout << “\nEnter the number of elements : “;
cin >> n;
int arr[n];
cout << “\nInput the array elements : “;
for(int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << “\nEquilibrium Index : ” << equilibrium_index(arr, n);
return 0;
}

public class Main
{
static int equilibrium_index(int arr[], int n)
{
int sum = 0;
int leftsum = 0;

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;
}

public static void main(String[] args)
{
int arr[] = { 1,2,3,4,5,1,3,2,4 };
int arr_size = arr.length;
System.out.print(“Equilibrium Index : “);
System.out.println(equilibrium_index(arr, arr_size));
}
}

def equilibrium_index(arr):
total_sum = sum(arr)
leftsum = 0
for i, num in enumerate(arr):
total_sum -= num

if leftsum == total_sum:
return i
leftsum += num

return -1

arr = [1,2,3,4,5,1,2,3,4]
print(“Equilibrium Index : “, end = “”)
print (equilibrium_index(arr))

Output:

equilibrium index of an array

Time complexity: O(n)