What is Prefix Sum?
Prefix Sum is the summation of some consecutive values in an array .
Let's see a problem -
**Given an array of integers, find the equilibrium index. An equilibrium index is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.
Example:
Input
7
-7 1 5 2 -4 3 0
Output
3
Explanation: At index 3, the sum of elements before it is -1 and after it is also -1
-7
1
5
2
-4
3
0
Sum of before index 3 = -7 + 1 + 5 = -1
Sum of after index 3 = -4 + 3 + 0 = -1
**
Example of an array - 1 2 3 4 5
Output - Index number of (lower sum = Higher Sum)
If found write index number else -1
`#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
vector<int> v(n);
int totalSum = 0;
for (int i = 0; i < n; i++)
{
cin >> v[i];
totalSum += v[i];
}
int ans = -1;
vector<int> pref(n);
pref[0] = v[0];
for (int i = 1; i < n; i++)
{
pref[i] = pref[i - 1] + v[i];
}
for (int i = 0; i < n; i++)
{
int rightSum = totalSum - pref[i];
if (pref[i] == rightSum)
{
ans = i;
break;
}
}
cout << ans << '\n';
}`
Top comments (0)