Last Updated: 1 Apr, 2021

Count Of Range Sum

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 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.

Solve now

02 Approach

Approach:

In this solution using merge sort, we count the answer while doing the merge. During the merge stage, we have already sorted the left half [start, mid) and right half [mid, end).

We then iterate through the left half with index i. For each i, we need to find two indices k and j in the right half where j is the first index satisfy sums[j] - sums[i] > R and k is the first index satisfy sums[k] - sums[i] >= L.

Then the number of sums in [L, R] is j - k.

Algorithm:

Function to count subarrays using merge sort. int mcount(int [] sum, int L, int R, int start, int end)

Firstly deal with the corner cases, if end-start >= 0, then return 0.
Intialise variable mid where mid = (start + end)/2, m = n = mid.
Then intialise a variable count, and update it as count= mcout(sum,L,R,start,mid) + mcount(sum,L,R,mid,end)
Iterate i from 0 to mid.
- While(m<end and sum[m]-sum[i]<L) m++
- while(n<end and sum[n]-sum[i]<=R) n++
- Update count as count+=n-m.
Return count.

Function to calculate the number of sum range int countRangeSum(int [] nums, int L, int R).

Initialize an array of long long int(to avoid int overflows) sum of length equal to the length of nums+1.
Iterate i from 0 to n, and update sum as sum[i+1]=sum[i]+nums[i]
Then return the value obtained by the pervious function mcount(sum,L,R,0,n+1).

Solve now