PREFPRO3 - Editorial

editorial
1

Prerequisite :- Prefix Sum.

Explanation :-

Check over each subarray, whether it is a good subarray or not.
Logic1 :-
A total (N * ( N+1 ) ) / 2 subarrays are possible in an array.
Sum of a subarray can be found by Iterating over a subarray, which will cost us around ~O(N) time.
Iterating over each subarray, make the time complexity ~ O(N3)

Logic2 :-
Finding the sum of a subarray can be optimized from O(N) to O(1) using a prefix array.
Time complexity using prefix sum ~ O(N2)

C++ Solution :-

#include <bits/stdc++.h>
using namespace std;

int main() {
    // your code goes here
    int n, k;
    cin >> n >> k;
    vector < int > v1;
    for (int i = 0; i < n; i++) {
        int n1;
        cin >> n1;
        v1.push_back(n1);
    }
    vector < int > pre(n, 0);
    for (int i = 0; i < n; i++) {
        if (i != 0) {
            pre[i] += pre[i - 1];
        }
        pre[i] += v1[i];
    }
    int fans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (i == j) {
                if (v1[i] == k) fans++;
            }
            else {
                if (i == 0) {
                    if (pre[j] == k) {
                        fans++;
                    }
                }
                else if(pre[j] - pre[i-1] == k){
                    fans++;
                }
            }
        }
    }
    cout << fans << "\n";
}