# Play With Numbers Programming Challenge (mean value of subarrays)

I'm trying to solve this Play With Numbers. I have passed the test cases but, I kept getting time limit exceeded. Can someone help me improve its performance in order to pass the time limit, please?

Problem

You are given an array of n numbers and q queries. For each query you have to print the floor of the expected value(mean) of the subarray from L to R.

Input

First line contains two integers N and Q denoting number of array elements and number of queries.

Next line contains N space seperated integers denoting array elements.

Next Q lines contain two integers L and R(indices of the array).

Output

print a single integer denoting the answer.

Time Limit:

1.5 sec(s) for each input file.

Result Time:

Input 1: 1.999309
Input 2: 1.998019

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int n = 0, q = 0;
cin >> n >> q;

vector<int> nums(n);

for (size_t i = 0; i < n; i++)
{
cin >> nums[i];
}

for (size_t i = 0; i < q; i++)
{
float ans = 0.0f;
int leftIndex = 0, rightIndex = 0;

cin >> leftIndex >> rightIndex;

leftIndex = leftIndex - 1;
rightIndex = rightIndex - 1;

for (size_t i = leftIndex; i <= rightIndex; i++)
{
ans = ans + nums[i];
}

ans = ans / (rightIndex - leftIndex) + 1;
cout << floor(ans) << "\n";
}
system("pause");
}


You are running this O(R - L) loop for each query:

for (size_t i = leftIndex; i <= rightIndex; i++)
{
ans = ans + nums[i];
}


You could obtain each sum in O(1) time if you stored the array as cumulative sums instead.

\begin{align} S_1 =&\ A_1 \\ S_2 =&\ S_1 + A_2 \\ S_3 =&\ S_2 + A_3 \\ \vdots& \\ S_N =& S_{N-1} + A_N \end{align}

The tricky part is that $S_N$ could be as large as $10^{15}$, which requires more than 32 bits.

• I found out there's built-in function for this. It's called std::partial_sum – Sparcsky Aug 25 '17 at 0:21

Simply calculate the sum of array elements while taking them as input.

Do not use a for loop, for doing so for every l and r.

Also, divide by (r-l+1) (instead of (r-l)), as this gives the total numbers between l and r. I Hope it helps.