Write a program using C++ to find the number of subarrays with sum in a given range

In this article, we will use a C program to find the number of sub-arrays whose sum is within a given range. We have an array of positive integers arr[] and a range {L, R} and we have to count the total number of subarrays whose sum falls within the given range L to R. So here is a simple example of the problem -

Input : arr[] = {1, 4, 6}, L = 3, R = 8

Output : 3

The subarrays are {1, 4}, {4}, {6}.


Input : arr[] = {2, 3, 5, 8}, L = 4, R = 13

Output : 6

The subarrays are {2, 3}, {2, 3, 5}, {3, 5},
{5}, {5, 8}, {8}.

Methods to find the solution

We will explain two ways to solve this problem using C#-

Brute force method

The most basic brute force approach is to calculate the sum of each subarray and then find whether that sum exists within a given range. (But this approach will take us a lot of time since its time complexity is O(n*n), where n is the size of the array).

Efficient method

Save Now, the efficient method is to use the sliding window technique, using this technique we will calculate the result faster or more efficiently in O(n).

Example

#include <bits/stdc++.h>
using namespace std;
int subCount(int *arr, int n, int x){
    int start = 0, end = 0, sum = 0, count = 0;
    while (end < n){ // we will be moving right border in this loop
        sum = sum + arr[end];
        while(start <= end && sum >= x){ // this loop will move our left border
            sum = sum - arr[start]; // we will decrement sum while moving left border.
                                   // For excluding the previous elements.
            start++;                // and move the left border.
        }
        count = count + ((end - start) + 1); // counting the subarrays.
        end++;
    }
    return count;
}
int main(){
    int arr[] = { 1, 4, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int L = 3;
    int R = 8;
    int answer;
    answer = subCount(arr, n, R)  - subCount(arr, n, (L - 1)); // Final Answer.
    cout << answer << "\n";
    return 0;
}

Output

3

Description of the above code

In this method, we count the number of subarrays whose sum is less than the upper limit of the given range , and then subtract the number of subarrays whose sum is less than the upper limit of the given range. Use the subcount function to get less than the lower limit of a given range.

Subcount function

This function uses the sliding window technique to find the count of a subarray with a count less than x.

First, we start with "end" and "start", Their values ​​are all 0. When we iterate over an array, we maintain the sum of the elements from beginning to end. After that, if our start is equal to end and the sum is greater than or equal to x, we start moving the start and keep decreasing the sum as we take elements out of the sum.

Until our sum becomes less than x or our start becomes greater than the end. Now we increase the count by the subarray count and then increase the right bound by 1. Now, after the outer loop ends, we return the total count of the subarray.

Conclusion

In this paper, we solved the problem of finding the number of subarrays whose sum is within a given range in O(n) time complexity using sliding window technique. We also learned about this problem from a C program and the complete way we can solve it easily (normally and efficiently). We can write the same program in other languages ​​like C, java, python etc.

The above is the detailed content of Write a program using C++ to find the number of subarrays with sum in a given range. For more information, please follow other related articles on the PHP Chinese website!