Play With Numbers Programming Challenge (mean value of subarrays)

Question

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");
 }

Answer 1

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.

• Sparcsky: I found out there's built-in function for this. It's called std::partial_sum

Answer 2

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.