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.

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.