DEV Community

Mujahida Joynab
Mujahida Joynab

Posted on

Prefix Sum

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';
}`
Enter fullscreen mode Exit fullscreen mode

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay