1
\$\begingroup\$

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");
 }
\$\endgroup\$
4
\$\begingroup\$

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.

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.