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).
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains an integer ‘N’ denoting the number of elements in the given array/list 'SEQUENCE'.
The second line of each test case contains ‘N’ space-separated integers denoting the elements in the 'SEQUENCE'.
For each test case, return a sequence of equilibrium indices. If no such index exists, return an empty sequence.
You don't need to print the output, it has already been taken care of. Just implement the given function.
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
2
7
-7 1 5 2 -4 3 0
5
1 2 3 4 5
3 6
(Empty Sequence)
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.
2
7
-2 1 9 2 -6 3 0
4
100 -99 2 1
2
2
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
Try to find the sum of elements present at the lower and higher indices of the equilibrium index.
For an index to be at equilibrium we need to calculate the sum of all the elements present at indices lower than the index and the sum of all the elements present at indices higher than the index. If both the sums match then we can add that index to the sequence of equilibrium indices. Hence, for a given sequence we can iterate through each of the indexes and store it as ‘currentIndex’.
Now iterate through all the elements present at indices lower than ‘currentIndex’ and store it as ‘lowerSum’. Similarly, iterate through all the elements present at indices higher than ‘currentIndex’ and store it as ‘higherSum’. If ‘lowerSum’ matches ‘higherSum’ than the ‘currentIndex’ is at equilibrium and we add it to the answer sequence, else we traverse further in the sequence.
Once we complete the traversal we can return the answer sequence, which contains all the equilibrium indices or empty sequence in case of no equilibrium indices.
O(N^2), Where ‘N’ denotes the number of elements present in the sequence.
Since iteration through total N elements will take O(N) time and find the sum of elements to the left and right independently will take O(N) time for the each outer iteration element. Thus the overall time complexity will be O(N^2).
O(1).
Since we are using constant space and thus the space complexity will be O(1).
All tags
Sort by
Interview problems
....Easy cpp solution....
vector<int> findEquilibriumIndices(vector<int> &sequence)
{
int n=sequence.size();
vector<int>v;
int sum=0;
for(int i=0;i<n;i++)
{
sum+=sequence[i];
}
int ls=0;
for (int i = 0; i < n; i++)
{
sum -= sequence[i];
if (ls == sum) {
v.push_back(i);
}
ls += sequence[i];
}
return v;
}
Interview problems
SImple JAVA Solution Using Prefix Sum
import java.util.ArrayList;
public class Solution {
public static ArrayList<Integer> findEquilibriumIndices(int[] sequence) {
// Write your code here.
int[]prefixSum = new int[sequence.length];
int[]suffixSum = new int[sequence.length];
int i = 0;
int j =sequence.length-1;
prefixSum[i]=sequence[i];
suffixSum[j]=sequence[j];
for(i++,j--;i<sequence.length&&j>=0;i++,j--){
prefixSum[i]=prefixSum[i-1]+sequence[i];
suffixSum[j]=suffixSum[j+1]+sequence[j];
}
ArrayList<Integer> list = new ArrayList<>();
for(i=0;i<sequence.length;i++){
if(prefixSum[i]==suffixSum[i]) list.add(i);
}
return list;
}
}Interview problems
c++ solution of equilibrium indices
#include <bits/stdc++.h>
vector<int> findEquilibriumIndices(vector<int> &sequence) {
// Write your code here
int n = sequence.size();
vector<int> equilibriumIndices;
int totalSum = 0;
for (int i = 0; i < n; ++i) {
totalSum += sequence[i];
}
int leftSum = 0;
for (int i = 0; i < n; ++i) {
totalSum -= sequence[i]; // Subtract the current element from the total sum
if (leftSum == totalSum) {
equilibriumIndices.push_back(i);
}
leftSum += sequence[i]; // Add the current element to the left sum for the next iteration
}
return equilibriumIndices;
}
Interview problems
JAVA sol:)
import java.util.*; import java.io.*;
public class Solution { public static ArrayList<Integer> findEquilibriumIndices(int[] sequence) { ArrayList<Integer> ans = new ArrayList<>(); int tot = 0; for (int i = 0; i < sequence.length; i++) { tot += sequence[i]; } int pre = 0; int cur = tot; for (int i = 0; i < sequence.length; i++) { cur -= sequence[i]; if (pre == cur) ans.add(i); pre += sequence[i]; } return ans; } }
Interview problems
Equilibrium indices of a Sequence
#include <bits/stdc++.h>
vector<int> findEquilibriumIndices(vector<int> &sequence) {
int sumofSequence = 0;
for(int i = 0; i < sequence.size(); i++)
sumofSequence += sequence[i];
int leftSum = 0;
vector<int> ans;
for(int i = 0; i < sequence.size(); i++){
sumofSequence -= sequence[i];
if(sumofSequence == leftSum){
ans.push_back(i);
}
leftSum += sequence[i];
}
return ans;
}
my JS solution
function main() {
const t =+readLine();
for(let lt=0;lt<t; lt++){
const n = +readLine();
const arr = readLine().trim().split(' ').map(e=>+e);
let tot = arr.reduce((a,b)=>a+b);
let pre = 0;
let cur = tot;
let ans =[];
let i =0;
while(i<n){
cur -=arr[i];
if(pre==cur)ans.push(i);
pre +=arr[i];
i++
}
console.log(ans.join(' '))
}Interview problems
Discussion thread on Interview Problem | Equilibrium indices of a Sequence
Hey everyone, creating this thread to discuss the interview problem - Equilibrium indices of a Sequence.
Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Equilibrium indices of a Sequence
