Count Of Range Sum

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
0 upvote
Asked in companies
ThalesUrban Company (UrbanClap)Walmart

Problem statement

You are given an array “Nums” of size ‘N’ and two numbers ‘L,’ ‘R.’ Your task is to return the number of range sum that lies between L and R, both inclusive, where L<=R.

Range sum R(i,j) represents the sum of numbers between the index i to j in Nums. where i <= j.

Example : 
Let nums = [1, 2, 3], L = 2, R = 7

Then the possible ranges are [1,1],[2,2],[0,1],[1,2],[0,2], and their sum is 2,3,3,5,6 respectively. Hence the answer will be 5.

Note: Assume zero based indexing.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains an integer N.
The second line of each test case contains N space-separated integers denoting the elements of the array.
The third line of each test case contains two space-separated integers L and R.
Output Format : 
For each test case, return an integer representing the number of range sum.

Output for each query is printed in a separate line.

Note: You don’t need to print anything or take input. This already has been taken care of. Just implement the function.
Constraints : 
1 <= T <= 10 
1 <= N <= 10^4
-2^31 <= Nums[i] <= 2^31-1
-3*10^4 <= L <= R <= 3*10^4

where T is the number of test cases, 'N' is the number of elements in the array, Num[i] is the elements of the array num, and 'L' and 'R' are the given range. 

Time Limit: 1 sec
Sample Input 1 :
2
3
-2 5 -1
-2 2
1
0
0 0
Sample output 1 :
3
1
Explanation :
Test case 1
In this case the possible range sum are [0, 0], [2, 2], [0, 2] and their sums are -2, -1, 2 respectively. So the answer would be 3.

Test case 2
In this case, the possible range sum is [0, 0] whose sum is 0. Hence the answer would be 1.
Sample Input 2 :
2
4
1 -2 4 6
-3 2
1
3
4 5
Sample output 2 :
4
0
Hint

check every possible range

Approaches (2)
Naive Approach

The naive approach to this problem will check all subarrays of Nums and if their range lies between L and R, then increase the count.

Algorithm:

  • Initialise  variable count=0, temp=0.
  • Iterate i from 0 to size of the array - 1. This would decide the starting point of our subarrays.
    • Update  temp=0 every time in this loop.
    • Iterate j from i to the size of array-1. This would decide the ending point of our subarrays.
      • Update temp as temp+=Nums[j];
      • If temp>=L or temp<=R then increase count by 1.
  • Return count.
Time Complexity

O(N^2), where N is the size of the array.

 

For finding the sum of all subarrays, we are iterating i N times as well as j N - 1 time. So the complexity will be O(N^2).

Space Complexity

O(1)

 

No extra space is used.

Code Solution
(100% EXP penalty)
Count Of Range Sum
Full screen
Console