Sum Of Infinite Array

Moderate

0/80

Average time to solve is 35m

3454 upvotes

Asked in companies

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”(1-based indexing). 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.

Note :

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

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run.

Then the T test cases follow. 

The first line of each test case contains a single integer N, denoting the size of the array “A”.

The second line of each test case contains N single space-separated integers, elements of the array “A”.

The third line of each test case contains a single integer Q, denoting the number of queries.

Then each of the Q lines of each test case contains two single space-separated integers L, and R denoting the left and the  right index of the infinite array “B” whose sum is to be returned.

Output format :

For each test case, print Q space-separated integers that denote the answers of the given Q queries. 
Print the answer to each test case in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

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

Sample Input 1 :

Sample Output 1 :

6 9

Explanation to Sample Input 1 :

For the first test case, the given array A is [1,2,3] therefore the infinite array “B” will be [1,2,3,1,2,3,1,2,3,.......]. So the answer for the given first query is 6 because the sum of the subarray from index 1 to 3 of infinite array “B” i.e. (B[1]+B[2]+B[3]) is 6.

For the given second query is 9 because the sum of the subarray from index 1 to 5 of array “B” .ie (B[1]+B[2]+B[3]+B[4]+B[5]) is 9.

Sample Input 2 :

Sample Output 2 :

27 22 28

Hint 1

Hint 2

Think of a solution to iterate the given array again and again instead of creating a new infinite array.

Approaches (2)

Approach 1

Approach 2

Brute Force

Instead of creating a new infinite array B which has a repeated array A elements in the form [A1, A2,... AN, A1, A2,... AN, A1, A2,... AN…....]. We will traverse array A, again and again, to find the sum as array A is only repeating in infinite array B.
So the brute force approach is, for each query,
- we run a loop from L to R, and for each index i, add the value at index (i%N) of the array A i.e A[i%N] to sum. So this way we can find the sum of the required subarray from index L to R in an infinite array B.

Time Complexity

O(Q*(R-L)) per test case, where Q is the number of given queries, and L and R are the given two indexes in each query.

In the worst case, for each query O(Q), we will be running a loop from L to R that takes (O(R-L)) time. Thus a total of O(Q*(R-L)) time will be required.

Space Complexity

O(1)

In the worst case, only a constant space is required.

(100% EXP penalty)

Sum Of Infinite Array

Console