CodingGyan

Equilibrium Index

medium Arrays

Problem

Print the smallest index where the sum of the elements on the left is equal to the sum of the elements on the right (the element itself is not counted). Print -1 if there is no such index.

Constraints

  • 1 <= n <= 10^5

Examples

Input

6
1 7 3 6 5 6

Output

3

Solutions

Best approachTime O(n)Space O(1)

Computing the right sum from scratch for each index costs O(n^2). With the total sum known, the right sum is total - left - element, so one pass is enough.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process an array.
 * Input   : n, then n integers.
 * Output  : The index or -1.
 * Approach: Prefix sum and total.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int solve(int[] a) {
        // Step 1: The total sum of all elements.
        long total = 0;
        for (int value : a) {
            total += value;
        }

        // Step 2: leftSum = the sum of the elements before index i.
        long leftSum = 0;
        for (int i = 0; i < a.length; i++) {
            // Step 3: The right sum is the total minus the left sum minus the element itself.
            long rightSum = total - leftSum - a[i];
            if (leftSum == rightSum) {
                return i;
            }
            leftSum += a[i];
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(solve(a));
    }
}
Hints (1)
  1. How do you get the right sum without a second loop?

Try these next