In this HackerEarth Finding the subarrays problem solution You are given an array A of N elements. You need to find all the subarrays such that their average sum is greater than the average sum of the remaining array elements. You need to print the start and end index of each subarray in sorted order in a new line.


HackerEarth Finding the Subarrays problem solution


HackerEarth Finding the Subarrays problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "\n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){ a%=m;LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
LL psum[10001];
LL a[10001];
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<pair<int,int> > ans;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        psum[i] = psum[i - 1] + a[i];
    }
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++) {
            double cur_sum = psum[j] - psum[i - 1];
            double cur_num = j - i + 1;
            double rem_sum = psum[n] - cur_sum;
            double rem_num = n - cur_num;
            double cur_avg = cur_sum / cur_num;
            double rem_avg;
            if(rem_num == 0)
                rem_avg = 0;
            else
                rem_avg = rem_sum / rem_num;
            if(cur_avg > rem_avg)
                ans.push_back({i , j});        
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); i++) {
        cout << ans[i].first << " " << ans[i].second << endl;
    }
}