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
• C++
• Java
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

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

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

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

  }
}

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

 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();

 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();

 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()

  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()

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

 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();

  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).