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
- The
get_sum
function calculates the sum of elements in a subarray from indexstart
tolast
. - The
equilibrium_indices
function takes the array and its size as parameters. - It iterates through each index
i
in the array. - 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 usingget_sum(arr, i + flag, size)
. - If these sums are equal, it prints the index and sets
status
to1
. - 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 inO(n)
time, wheren
is the size of the subarray. - The
equilibrium_indices
function iterates through each index, and for each index, it calculates two subarray sums using theget_sum
function. Therefore, the overall time complexity of the algorithm isO(n^2)
.
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.
New Comment