Equilibrium Index

Problem Statement: 
       Find the index in an array where sum of the numbers to its right is equal to the sum of the number to its right.

Fig1: Calculate total sum of element

Fig2: Keep subtracting right sum from total sum and compare

Solution:
Run Source Code

In the above example we first calculate the TotalSum of all the numbers in one traversal.
Maintain another cumulative sum from the right end of the array except the current element and keep on subtracting the RightSum from TotalSum. If at any point TotalSum becomes equal to RightSum, return the index.

Below is the implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

/** * Find the index in an array where sum to left is equal to sum to its right * @author PRATEEK */ public class EquilibriumIndex { /** * @param arr: input arr * @return : equilibrium index in the array */ private int equilibrium(int[] arr) { int i = 0, sum = 0, rightSum = 0; for (; i < arr.length; sum += arr[i++]); for (i--; i > 0; sum -= arr[i], rightSum += arr[i]) if (sum == rightSum - arr[i--]) return i; return -1; } public static void main(String[] args) { int arr[] = { -7, 1, 6, 2, -4, 3, 1 }; EquilibriumIndex obj = new EquilibriumIndex(); int mid = obj.equilibrium(arr); System.out.println(mid); } }

Time Complexity: O(n)
Space Complexity: O(1)

Please comment and post if any suggestions.
Happy Coding !!:)