# HackerEarth Equal subarrays problem solution

In this HackerEarth Equal subarrays problem solution You are given an array of N non-negative integers [A1,A2,A3,...,AN], and a non-negative integer K. A subarray is an array composed of a contiguous block of original array elements. You can perform the following operation on a subarray:

Increase each element of this subarray by a non-negative number such that the total sum of all the increments does not exceed K. You must make all the elements of this subarray equal.

Determine the maximum length of a subarray in which all the elements can be made equal by performing the mentioned operation.

## HackerEarth Equal subarrays problem solution.

`#include "bits/stdc++.h"using namespace std;int segment_tree[1000000];long long int A[100005];    int build(int start, int end, int node){    if(start == end)    {        segment_tree[node] = A[start];    }    else    {        int mid = (start + end) / 2;        segment_tree[node] = max(build(start, mid, 2*node + 1), build(mid+1, end, 2*node+2));    }    return segment_tree[node];}int query(int start, int end, int l, int r, int node){    if(start > r || end < l) return -1;    if(start >= l && end <= r) return segment_tree[node];    int mid = (start + end) / 2;    return max(query(start, mid, l, r, 2*node+1), query(mid+1, end, l, r, 2*node+2));}int main(){    int N; cin>>N;    int K; cin>>K;      for(int i=0; i<N; i++)    {        cin>>A[i];    }    long long int pref[N+1];    pref[0] = 0;    for(int i=0; i<N; i++)    {        pref[i+1] = pref[i] + A[i];    }    build(0, N-1, 0);    int ans = 1;    for(int i=0; i<N; i++)    {        int start = i, end = N-1, mid, max_index = i;        while(start <= end)        {            mid = (start + end) / 2;            long long int max_element = query(0, N-1, i, mid, 0);            long long int expected_sum = (mid - i + 1) * max_element;            long long int actual_sum = pref[mid + 1] - pref[i];            if(expected_sum - actual_sum <= K)            {                start = mid + 1;                max_index = max(max_index, mid);            }            else            {                end = mid - 1;            }        }        ans = max(ans, max_index - i + 1);    }    cout<<ans;    return 0;}`

### Second solution

`#include "bits/stdc++.h"using namespace std;typedef long long ll;const int maxn = 1e5 + 10, maxlg = 18;int n, k, a[maxn], mx[maxlg][maxn];ll par[maxn];int get(int l, int r) {    if (r <= l) return 0;    int lg = 31 - __builtin_clz(r - l);    return max(mx[lg][l], mx[lg][r - (1 << lg)]);}int main(){    cin >> n >> k;    for (int i = 0; i < n; ++i) {        cin >> a[i];        mx[0][i] = a[i];        par[i + 1] = par[i] + a[i];    }    for (int i = 1; i < maxlg; ++i)        for (int j = 0; j < n; ++j) {            mx[i][j] = mx[i - 1][j];            if (j + (1 << (i - 1)) < n)                mx[i][j] = max(mx[i][j], mx[i - 1][j + (1 << (i - 1))]);        }    int ans = 0;    for (int i = 0; i < n; ++i) {        int b = i, e = n, mid;        while (e - b > 1) {            mid = (b + e) >> 1;            ll val = get(i, mid + 1) * ll(mid - i + 1) - (par[mid + 1] - par[i]);            if (val <= k)                b = mid;            else                e = mid;        }        ans = max(ans, e - i);    }    cout << ans << '\n';    return 0;}`