'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Topics

Equilibrium indices of a Sequence

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
13 upvotes
Asked in companies
AccentureSpringworksVMware Inc

Problem statement

You have been given an array/list 'SEQUENCE' denoting the sequence of 'N' integers. Your task is to find the equilibrium indices of the sequence in 'SEQUENCE'.

The equilibrium index of a sequence of integers is defined as the index such that the sum of all the elements at lower indices is equal to the sum of elements at higher indices.

Note:
1. 'SEQUENCE' may contain more than one equilibrium indices.

2. If there are no equilibrium indices, return an empty sequence.

3. Consider the sum of elements lower than the first index and higher than the last index to be 0 (zero).
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 50
1 <= N <= 10^4
-10^9 <= SEQUENCE[i] <= 10^9

Where 'SEQUENCE[i]' denotes the elements of the array 'SEQUENCE'.

Time limit: 1 sec
Sample Input 1:
2
7
-7 1 5 2 -4 3 0
5
1 2 3 4 5
Sample Output 1:
3 6
                  (Empty Sequence)
Explanation of Sample Output 1 :
In test case 1, in the given sequence of indices, index 3 (consider 0 based indexing) is the equilibrium index, because the sum of the elements present at the indices lower than 3 i.e [-7 + 1 + 5 = 1 ] is equal to sum of all the elements present at indices higher than 3 i.e [ -4 + 3 + 0 = 1]. Similarly, for index = 6 the sum of elements at lower indices [-7+1+5+2+(-4)+3] is equal to the sum of higher indices(since it is the last element, the sum of higher indices is 0 as explained above). Hence we return the sequence [3, 6] which are the equilibrium indices.

In test case 2, for each index, we find the sum of all the values present at indices lower than the index and greater than the index. Consider index = 2, sum of elements present at indices lower than 2 is (1+ 2 = 3), and the sum of elements present at indices higher than 2 is (4 + 5 = 9), Because the sum doesn’t match, the index 2 is not at equilibrium. We can check in a similar way for all the indices of the sequence and conclude no index satisfies the equilibrium condition, therefore we return an empty sequence.
Sample Input 2:
2
7
-2 1 9 2 -6 3 0
4
100 -99 2 1
Sample Output 2:
2
2
Explanation of Sample Output 1 :
In test case 1, in the given sequence of indices, index 2 (consider 0 based indexing) is the equilibrium index, because the sum of the elements present at the indices lower than 2 i.e [-2 + 1 = -1 ] is equal to sum of all the elements present at indices higher than 2 i.e [ 2 + -6 + 3 + 0 = -1]. Hence we return the sequence [2] which is the equilibrium index.

In test case 2, for each index, we find the sum of all the values present at indices lower than the index and greater than the index. Consider index = 2, Sum of elements present at indices lower than 2 is (100 - 99 = 1), and the sum of elements present at indices higher than 2 is (1). Hence we return the sequence [2] which is the equilibrium index
Full screen
Console