New update is available. Click here to update.
sidenav-btnClose
Topic list
Sum Of Infinite Array
MEDIUM
35 mins
2970 upvotes
Dynamic Programming
Arrays
Topics (Covered in this problem)
Problem solved
Skill meter
Dynamic Programming
-
Arrays
-
Other topics
Problem solved
Skill meter
Strings
-
Matrices (2D Arrays)
-
Sorting
-
Binary Search
-
Linked List
-
Stacks & Queues
-
Trees
-
Graph
-
Greedy
-
Tries
-
Binary Search Trees
-
Heap
-
Bit Manipulation
-

Sum Of Infinite Array

Contributed by
Ashwani
Medium
Avg time to solve 35 mins
Success Rate 70 %
Share
2970 upvotes

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, Constraints, Images )
Sample Input 1 :
1
3
1 2 3
2
1 3
1 5
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 :
1
4
5 2 6 9
3
1 5
10 13
7 11
Sample Output 2 :
27 22 28
Reset Code
Full screen
copy-code
Console