Problem

Submissions

Hints & solutions

Discuss

Range Sum

Moderate

0/80

Average time to solve is 10m

Contributed by

10 upvotes

Asked in companies

Problem statement

You are given an array ‘arr’ of size ‘N’. You are provided with ‘Q’ queries, each containing two integers, ‘L’ and ‘R’. Your task is to return the sum of elements from the position ‘L’ to ‘R’ for each query.

For example:

You are given arr = [1, 3, 4, 5, 6, 9], and queries = [[1, 3], [5, 6] , [1, 6]].

For the first query [1, 3] sum of elements = 1 + 3 + 4 = 8. Hence the answer is 8

For the second query [5, 6] sum of elements = 6 + 9 = 15. Hence the answer is 15

For the third query [1, 6] sum of elements = 1 + 3 + 4 + 5 + 6 + 9= 28. Hence the answer is 28. 

Hence the final answer is [8, 15, 28]

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

Input Format:

The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘Q’, denoting the size of the array and the number of queries.

The second line contains ‘N’ space-separated integers representing the elements of the array ‘arr’.

The next ‘Q’ lines contain two space-separated integers, ‘L’ and ‘R’ representing each query.

Output Format:

For each test case, print ‘Q’ space-separated integers, denoting the sum of elements for each query.

The output of each test case will be printed in a separate line.

Constraints:

1 <= T <= 10 
1 <= N, Q <= 10 ^ 6
0 <= arr[i] <= 10 ^ 8
1 <= L <=  R <= N

Time limit: 1 sec

Note:

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

Sample Input 1:

2
6 3
1 3 4 5 6 9
1 3
5 6
1 6
3 1 
1 1 1
1 3

Sample Output 1:

8 15 28
3

Explanation:

For the first test case, arr = [1, 3, 4, 5, 6, 9], and queries = [[1, 3], [5, 6] , [1, 6]].
For the first query [1, 3] sum of elements = 1 + 3 + 4 = 8. Hence the answer is 8
For the second query [5, 6] sum of elements = 6 + 9 = 15. Hence the answer is 15
For the second query [1, 6] sum of elements = 1 + 3 + 4 + 5+ 6 + 9= 28. Hence the answer is 28. Hence the final answer is [8, 15, 28]

For the second test case arr = [1, 1, 1] and queries = [[1, 3]]
For the first query [1, 3] sum of elements = 1 + 1 + 1 = 3. Hence the answer is 3. Hence the final answer is [3].

Sample Input 2:

Sample Output 2:

3 0
10002

Hint 1

Hint 2

Find the solution of each query by traversing through the array.

Approaches (2)

Approach 1

Approach 2

Brute Force

In this approach, we will maintain an array, and for each query, we will take the sum from range L to R and store the sum in the array.

Algorithm:

Initialise an empty array ans.
Iterate query through the queries array
- Set rSum as 0
- Iterate i from query[0] - 1 to query[1] - 1
  - Add arr[i] to rSum
- Insert rSum into the array arr
Finally, return arr

Time Complexity

O(N*Q), where N is the size of the array and Q is the number of queries.

For each query, we are iterating over the array that will cost O(N) time. Hence the final time complexity is O(N*Q).

Space Complexity

O(Q), where Q is the number of queries.

Since we will return our answers to all the queries in an array, the final space complexity is O(Q).

(100% EXP penalty)

Range Sum

Console