Problem Statement:

Given an array “A” of N integers and you have also defined the new array “B” as a concatenation of array “A” for an infinite number of times. For example, if the given array “A” is [1,2,3] then, infinite array “B” is [1,2,3,1,2,3,1,2,3,.......]. Now you are given Q queries, each query consists of two integers “L“ and “R”. Your task is to find the sum of the subarray from index “L” to “R” (both inclusive) in the infinite array “B” for each query.

vector<int> sumInRanges(vector<int> &arr, int n, vector<vector<long long>> &queries, int q) {
    
    vector<int> ans;
    for(int i=0; i<q; i  ){
        int l = queries[i][0];
        int r = queries[i][1];
        int sum = 0;
        for(int j=l-1; j<r; j  ){
            sum  = arr[j%n];
        }
        ans.push_back(sum);
    }
    return ans;
}

One test case is failing. Could someone suggest the edit required?

CodePudding user response：

Good I've found link to your actual problem.

Take a look on note:

Sum Of Infinite Array

Note :

The value of the sum can be very large, return the answer as modulus 10^9 7.

....

Constraints :

1 <= T <= 100
1 <= N <= 10^4   
1 <= A[i] <= 10^9
1 <= Q <= 10^4
1 <= L <= R <= 10^18

Time Limit: 1sec

So basically your code have problem with integer overflow.

Your implementation is to simple. You have to leverage fact that this infinitive array has a period otherwise your code never meets time requirement. You do not have to calculate sum of the all indexes, you can skip a lot and calculate correction using multiplication (modulo).

CodePudding user response：

Your solution takes time proportional to l - r because it tries every number.

But this is unnecessary, as there are n identical periods that you can sum in a single go. So the running time can be made proportional to the length of A instead. (Find the multiple of the length just above or on l and the multiple just below r.)

E.g. to sum from 10 to 27 inclusive, use

1231231231|231231231231231231|23123123... = 1231231231|23 4x123 1|23123123...