Number of subarrays having sum in a given range using Nested loops
The basic approach to solve this type of question is to try all possible case using brute force method and count all the pair whose sum lie in the range [lower, uppper].
Below is the implementation of the above approach:
#include <iostream>
#include <vector>
using namespace std;
int getCount(vector<int> arr, int n, int lower, int upper)
{
int count = 0;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += arr[j];
if (sum >= lower and sum <= upper) {
count++;
}
}
}
return count;
}
int main()
{
int n = 4;
vector<int> arr = { -2, 4, 1, -2 };
int lower = -4, upper = 1;
int answer = getCount(arr, n, lower, upper);
cout << answer << endl;
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class Main {
// Function to get the count of subarrays with sum in
// the given range [lower, upper]
static int getCount(List<Integer> arr, int n, int lower,
int upper)
{
int count = 0;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += arr.get(j);
if (sum >= lower && sum <= upper) {
count++;
}
}
}
return count;
}
public static void main(String[] args)
{
int n = 4;
List<Integer> arr = new ArrayList<>();
arr.add(-2);
arr.add(4);
arr.add(1);
arr.add(-2);
int lower = -4, upper = 1;
int answer = getCount(arr, n, lower, upper);
System.out.println(answer);
}
}
def get_count(arr, lower, upper):
count = 0
n = len(arr)
for i in range(n):
sum_val = 0
for j in range(i, n):
sum_val += arr[j]
if lower <= sum_val <= upper:
count += 1
return count
def main():
n = 4
arr = [-2, 4, 1, -2]
lower = -4
upper = 1
answer = get_count(arr, lower, upper)
print(answer)
if __name__ == "__main__":
main()
// Function to count subarrays with sum in the range [lower, upper]
function getCount(arr, lower, upper) {
let count = 0;
const n = arr.length;
for (let i = 0; i < n; i++) {
let sum = 0;
for (let j = i; j < n; j++) {
sum += arr[j];
if (sum >= lower && sum <= upper) {
count++;
}
}
}
return count;
}
// Main function
function main() {
const n = 4;
const arr = [-2, 4, 1, -2];
const lower = -4, upper = 1;
const answer = getCount(arr, lower, upper);
console.log(answer);
}
// Call the main function
main();
Output
5
Time Complexity: O(n^2)
Auxiliary Space: O(1)
Number of subarrays having sum in a given range
Given an array arr[] of integers and a range (L, R). Find the number of subarrays having sum in the range L to R.
Examples:
Input: arr = { -2, 4, 1, -2}, lower = -4, upper = 1
Output: 5
Explanation: The pairs that are present here are –
- (1, 1) = [-2] , sum = -2
- (1, 4) = [-2, 4, 1, -2] , sum = 1
- (3, 3) = [1] , sum = 1
- (3, 4) = [1, -2] , sum = -1
- (4, 4) = [-2] , sum = -2
Input : arr[] = {2, 3, 5, 8}, L = 4, R = 13
Output : 6
Explanation: The subarrays are {2, 3}, {2, 3, 5}, {3, 5}, {5}, {5, 8}, {8}.