Find the equilibrium index of an array | faceprep

Find the equilibrium index of an array | faceprep

The program to find the equilibrium index of an array is discussed here. The equilibrium index of an array is an index such that


Find the Equilibrium Index of an Array

The 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.
  • The outer loop iterates through all the element and the inner loop check out whether the current index picked by the outer loop is either an equilibrium index or not.
  • The time complexity of this solution is O(n^2).



find-the-equilibrium-index-of-an-arrayProgram to find the equilibrium index of an array

@@coding::1@@

Time complexity: O(n^2)


find-the-equilibrium-index-of-an-array

Method 2:

Find the sum of the array and then traverse through the array and keep updating the left sum which is initially zero. To get the right sum, subtract the array values from the sum while traversing. Check the 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:
  • Update sum to get the right sum.
  • sum = sum – arr[i] // sum is the right sum.
  • If left_sum == sum, return current index.
  • Update left_sum = left_sum + arr[i]
  • Return -1 and exit the algorithm. // Equilibrium index is not found.


find-the-equilibrium-index-of-an-array

Program to find the equilibrium index of an array

@@coding::2@@

Time complexity: O(n)



Recommended Programs









find-the-equilibrium-index-of-an-array

c