Check if sum of left side of array equal to right side of array

Easy

0/40

2 upvotes

Problem statement

You are given an array Arr consisting of n integers. You need to find the equilibrium index of the array. An index is considered as equilibrium index if the sum of elements to the left of that index is equal to the sum of elements to the right of it.

Note:

The array follows 0-based indexing, so you need to return the 0- based index of the element. If there are multiple indices which satisfy the given condition, then return the left-most index. If no such index is present in the array, return -1.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer T, denoting the number of test cases.
The first line of each test case contains the integer N, denoting the size of the array.
The second line of each test case contains N space-separated integers denoting the array elements.

Output Format:

The only line of output of each test case contains a single integer which corresponds to the equilibrium index for the array.

#### Note : You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 10^5
0 <= Arr[i] <= 10^4
Time Limit: 1 sec

Sample Input 1:

1
6
1 7 3 6 5 6

Sample Output 1:

Explanation for Sample Input 1:

The sum of elements to the left of arr[3] = 1 + 7 + 3 = 11.
The sum of elements to the right of arr[3] = 5 + 6 = 11.
Hence the answer is 3.

Sample Input 2:

2
6
1 2 2 9 3 2
4
1 2 3 4

Sample Output 2:

-1

Explanation for Sample Input 2:

In the first test case of sample input 2, the sum of elements on the left of index 3 (arr[3] = 9) is five which is equal to the sum of elements on the right of arr[3].
For the second test case, since no such index exists, we print -1.

Hint 1

Hint 2

Hint 3

Naively find the answer for every index

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

We can try the brute force approach in which for every index, we can run a loop to the left of that index and to the right of that index, and check if the sum of elements is equal or not.
Let us initialise the ans = -1, which will contain our valid index.
Since index 0 and n - 1 cannot be possible candidates for the answer, we can start the loop from i = 1 to i = n - 2.
Now for every i, let leftSum = 0 and rightSum = 0.
For j = 0 to j = i - 1, do leftSum = leftSum + arr[j].
For k = i + 1 to k = n - 1, do rightSum = rightSum + arr[k].
If leftSum = rightSum, then return i.
After the loop of i ends, return -1, since we have not found a valid index.

Time Complexity

O(N^2), where N is the size of the array.

Space Complexity

O(1), as we are using constant extra memory.

(100% EXP penalty)

Check if sum of left side of array equal to right side of array

Console