Posted on by Kalkicode
Code Array

# Find Equilibrium index of given array

Finding the equilibrium index of a given array is a common problem in programming. An equilibrium index is an index in the array where the sum of elements to the left of that index is equal to the sum of elements to the right of that index.

## Problem Statement

Given an array of integers, find all the equilibrium indices. An equilibrium index is an index `i` such that the sum of elements at indices `0` to `i-1` is equal to the sum of elements at indices `i+1` to `n-1`, where `n` is the size of the array.

## Example

Consider the following array:

``arr = [1, 1, 1, 7, -7, 1, -2, 1, 7, 3]``

The equilibrium indices are `3`, `4`, and `8` because:

• For index `3`: sum of left subarray = `1 + 1 + 1`, sum of right subarray = `-7 + 1 - 2 + 1 + 7 + 3`
• For index `4`: sum of left subarray = `1 + 1 + 1 + 7`, sum of right subarray = `1 - 2 + 1 + 7 + 3`
• For index `8`: sum of left subarray = `1 + 1 + 1 + 7 - 7 + 1 - 2 + 1`, sum of right subarray = `3`

## Idea to Solve

To find equilibrium indices, iterate through each index and calculate the sum of elements on its left and right. Compare these sums; if they are equal, then the index is an equilibrium index.

## Pseudocode

``````function get_sum(arr, start, last):
sum = arr[start]
for i from start + 1 to last - 1:
sum += arr[i]
return sum

function equilibrium_indices(arr, size):
flag = 1
status = 0
for i from 0 to size - 1:
if i == size - 1:
flag = 0
if get_sum(arr, 0, i) == get_sum(arr, i + flag, size):
print(i)
status = 1
flag = 1
if status == 0:
print("No equilibrium index in this array")

// Example usage
arr = [1, 1, 1, 7, -7, 1, -2, 1, 7, 3]
size = size(arr)
equilibrium_indices(arr, size)``````

## Algorithm Explanation

1. The `get_sum` function calculates the sum of elements in a subarray from index `start` to `last`.
2. The `equilibrium_indices` function takes the array and its size as parameters.
3. It iterates through each index `i` in the array.
4. For each index, it calculates the sum of elements on its left using `get_sum(arr, 0, i)` and the sum of elements on its right using `get_sum(arr, i + flag, size)`.
5. If these sums are equal, it prints the index and sets `status` to `1`.
6. If no equilibrium indices are found, it prints a message indicating that there are no equilibrium indices.

## Code Solution

``````//C Program
//Equilibrium index of an given array
#include <stdio.h>

//returning the sum of subarray from start to last of given index
int get_sum(int arr[],int start,int last)
{

int sum=arr[start];

for(int i = start+1; i < last; i++)
{
sum += arr[i];
}
return sum;
}
void equilibrium_index(int arr[],int size)
{

int flag = 1;

int status = 0 ;

for(int i=0;i<size ;i++)
{
if(i==size-1)
{
//When last index
flag=0;
}
//Compare sum of left and right sub array
if(get_sum(arr,0,i) == get_sum(arr,i+flag,size))
{
//Print the resultant index
printf(" %d ",i);

status = 1;
}
flag=1;
}
if(status==0)
{
printf("No Equilibrium index in this array\n");
}

}

int main()
{
//Define array elements
int arr[]={1,1,1,7,-7,1,-2,1,7, 3};

//Get the size of array
int size = sizeof(arr)/sizeof(arr[0]);

equilibrium_index(arr,size);

return 0;
}```
```

#### Output

`` 3  4  8``
``````/*
C++ Program
Find Equilibrium index of an given array
*/
#include<iostream>
using namespace std;

class MyArray {
public:

//returning the sum of subarray from start to last of given index
int get_sum(int arr[], int start, int last) {
int sum = arr[start];
for (int i = start + 1; i < last; i++) {
sum += arr[i];
}
return sum;
}
void equilibrium_index(int arr[], int size) {
int flag = 1;
int status = 0;
for (int i = 0; i < size; i++) {
if (i == size - 1) {
//When last index
flag = 0;
}
//Compare sum of left and right sub array

if (this->get_sum(arr, 0, i) == this->get_sum(arr, i + flag, size)) {
//Get the resultant index

cout << " " << i;
status = 1;
}
flag = 1;
}
if (status == 0) {
cout << "No Equilibrium index in this array\n";
}
}
};
int main() {
MyArray obj ;
int arr[] = {
1,
1,
1,
7,
-7,
1,
-2,
1,
7,
3
};
//Count size of array
int size = sizeof(arr) / sizeof(arr[0]);
obj.equilibrium_index(arr, size);
return 0;
}```
```

#### Output

`` 3 4 8``
``````/*
Java Program
Find Equilibrium index of an given array
*/
public class MyArray {

//returning the sum of subarray from start to last of given index
int get_sum(int []arr,int start,int last)
{

int sum=arr[start];

for(int i = start+1; i < last; i++)
{
sum += arr[i];
}
return sum;
}
void equilibrium_index(int []arr,int size)
{

int flag = 1;

int status = 0 ;

for(int i=0;i<size ;i++)
{
if(i==size-1)
{
//When last index
flag=0;
}
//Compare sum of left and right sub array
if(get_sum(arr,0,i) == get_sum(arr,i+flag,size))
{
//Get the resultant index
System.out.print(" "+i);

status = 1;
}
flag=1;
}
if(status==0)
{
System.out.print("No Equilibrium index in this array\n");
}

}
public static void main(String[] args)
{

MyArray obj = new MyArray();
//Define array elements
int []arr={1,1,1,7,-7,1,-2,1,7, 3};

//Count size of array
int size=arr.length;

obj.equilibrium_index(arr,size);

}
}```
```

#### Output

`` 3 4 8``
``````/*
C# Program
Find Equilibrium index of an given array
*/
using System;

public class MyArray {
//returning the sum of subarray from start to last of given index
int get_sum(int[] arr, int start, int last) {
int sum = arr[start];
for (int i = start + 1; i < last; i++) {
sum += arr[i];
}
return sum;
}
void equilibrium_index(int[] arr, int size) {
int flag = 1;
int status = 0;
for (int i = 0; i < size; i++) {
if (i == size - 1) {
//When last index
flag = 0;
}
//Compare sum of left and right sub array

if (get_sum(arr, 0, i) == get_sum(arr, i + flag, size)) {
Console.Write(" " + i);
status = 1;
}
flag = 1;
}
if (status == 0) {
Console.Write("No Equilibrium index in this array\n");
}
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
//Define array elements
int[] arr = {
1,
1,
1,
7,
-7,
1,
-2,
1,
7,
3
};
//Count size of array
int size = arr.Length;
obj.equilibrium_index(arr, size);
}
}```
```

#### Output

`` 3 4 8``
``````<?php
/*
Php Program
Find Equilibrium index of an given array
*/
class MyArray {
//returning the sum of subarray from start to last of given index
function get_sum(\$arr, \$start, \$last) {
\$sum = \$arr[\$start];
for (\$i = \$start + 1; \$i < \$last; \$i++) {
\$sum += \$arr[\$i];
}
return \$sum;
}

function equilibrium_index(\$arr, \$size) {
\$flag = 1;
\$status = 0;
for (\$i = 0; \$i < \$size; \$i++) {
if (\$i == \$size - 1) {
//When last index
\$flag = 0;
}
//Compare sum of left and right sub array

if (\$this->get_sum(\$arr, 0, \$i) == \$this->get_sum(\$arr, \$i + \$flag, \$size)) {
//Get the resultant index

echo(" ". \$i);
\$status = 1;
}
\$flag = 1;
}
if (\$status == 0) {
echo("No Equilibrium index in this array\n");
}
}
}

function main() {
\$obj = new MyArray();
//Define array elements
\$arr = array(1, 1, 1, 7, -7, 1, -2, 1, 7, 3);
//Count size of array
\$size = count(\$arr);
\$obj->equilibrium_index(\$arr, \$size);

}
main();```
```

#### Output

`` 3 4 8``
``````/*
Node Js Program
Find Equilibrium index of an given array
*/
class MyArray {
//returning the sum of subarray from start to last of given index
get_sum(arr, start, last) {
var sum = arr[start];
for (var i = start + 1; i < last; i++) {
sum += arr[i];
}

return sum;
}
equilibrium_index(arr, size) {
var flag = 1;
var status = 0;
for (var i = 0; i < size; i++) {
if (i == size - 1) {
//When last index
flag = 0;
}

//Compare sum of left and right sub array

if (this.get_sum(arr, 0, i) == this.get_sum(arr, i + flag, size)) {
//Get the resultant index

process.stdout.write(" " + i);
status = 1;
}
flag = 1;
}

if (status == 0) {
process.stdout.write("No Equilibrium index in this array\n");
}
}
}

function main(args) {
var obj = new MyArray();
//Define array elements
var arr = [1, 1, 1, 7, -7, 1, -2, 1, 7, 3];
//Count size of array
var size = arr.length;
obj.equilibrium_index(arr, size);
}

main();```
```

#### Output

`` 3 4 8``
``````# Python 3 Program
# Find Equilibrium index of given array
class MyArray :
def get_sum(self, arr, start, last) :
sum = arr[start]
i = start + 1
while (i < last) :
sum += arr[i]
i += 1

return sum

def equilibrium_index(self, arr, size) :
flag = 1
status = 0
i = 0
while (i < size) :
if (i == size - 1) :
# When last index
flag = 0

# Compare sum of left and right sub array

if (self.get_sum(arr, 0, i) == self.get_sum(arr, i + flag, size)) :
print(" ", i, end = "")
status = 1

flag = 1
i += 1

if (status == 0) :
print("No Equilibrium index in this array\n", end = "")

def main() :
obj = MyArray()
arr = [1, 1, 1, 7, -7, 1, -2, 1, 7, 3]
size = len(arr)
obj.equilibrium_index(arr, size)

if __name__ == "__main__":
main()```
```

#### Output

``  3  4  8``
``````# Ruby Program
# Find Equilibrium index of given array
class MyArray
def get_sum(arr, start, last)
sum = arr[start]
i = start + 1
while (i < last)
sum += arr[i]
i += 1
end
return sum
end
def equilibrium_index(arr, size)
flag = 1
status = 0
i = 0
while (i < size)
if (i == size - 1)
# When last index
flag = 0
end
# Compare sum of left and right sub array

if (self.get_sum(arr, 0, i) == self.get_sum(arr, i + flag, size))
print(" ", i)
status = 1
end
flag = 1
i += 1
end
if (status == 0)
print("No Equilibrium index in this array\n")
end
end
end
def main()
obj = MyArray.new()
arr = [1, 1, 1, 7, -7, 1, -2, 1, 7, 3]
size = arr.length
obj.equilibrium_index(arr, size)
end
main()```
```

#### Output

`` 3 4 8``
``````/*
Scala Program
Find Equilibrium index of given array
*/
class MyArray {
def get_sum(arr: Array[Int], start: Int, last: Int): Int = {
var sum: Int = arr(start);
var i: Int = start + 1;
while (i < last) {
sum += arr(i);
i += 1;
}
return sum;
}
def equilibrium_index(arr: Array[Int], size: Int): Unit = {
var flag: Int = 1;
var status: Int = 0;
var i: Int = 0;
while (i < size) {
if (i == size - 1) {
//When last index
flag = 0;
}
//Compare sum of left and right sub array

if (this.get_sum(arr, 0, i) == this.get_sum(arr, i + flag, size)) {
print(" " + i);
status = 1;
}
flag = 1;
i += 1;
}
if (status == 0) {
print("No Equilibrium index in this array\n");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyArray = new MyArray();
val arr: Array[Int] = Array(1, 1, 1, 7, -7, 1, -2, 1, 7, 3);
val size: Int = arr.length;
obj.equilibrium_index(arr, size);
}
}```
```

#### Output

`` 3 4 8``
``````/*
Swift Program
Find Equilibrium index of given array
*/
class MyArray {
func get_sum(_ arr: [Int], _ start: Int, _ last: Int) -> Int {
var sum: Int = arr[start];
var i: Int = start + 1;
while (i < last) {
sum += arr[i];
i += 1;
}
return sum;
}
func equilibrium_index(_ arr: [Int], _ size: Int) {
var flag: Int = 1;
var status: Int = 0;
var i: Int = 0;
while (i < size) {
if (i == size - 1) {
//When last index
flag = 0;
}
//Compare sum of left and right sub array

if (self.get_sum(arr, 0, i) == self.get_sum(arr, i + flag, size)) {
print(" ", i, terminator: "");
status = 1;
}
flag = 1;
i += 1;
}
if (status == 0) {
print("No Equilibrium index in this array\n", terminator: "");
}
}
}
func main() {
let obj: MyArray = MyArray();
let arr: [Int] = [1, 1, 1, 7, -7, 1, -2, 1, 7, 3];
let size: Int = arr.count;
obj.equilibrium_index(arr, size);
}
main();```
```

#### Output

``  3  4  8``

## Time Complexity

• The `get_sum` function runs in `O(n)` time, where `n` is the size of the subarray.
• The `equilibrium_indices` function iterates through each index, and for each index, it calculates two subarray sums using the `get_sum` function. Therefore, the overall time complexity of the algorithm is `O(n^2)`.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post