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}.
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 using Merge Sort:
We will use Merge sort and prefix-sum to solve this problem. we will find the range from the small sorted arrays in the prefix array that lies in the range [lower, upper]. We use prefix array to track the sum and check if the pair lies in the range lower bound and upper bound then lower <= prefix[j] – prefix[i-1] <= upper or lower + prefix[i-1] <= prefix[j] <= upper + prefix[i-1]
Step-by-step approach:
- Calculate mid of the array by using (start + end)/2
- Then Recursivly call the function in two seperate half (start, mid) and (mid+1, end).
- After this Calls the two seperated array (start, mid) and (mid+1, end) are sorted in itself so we can calculate the range of the sum that lies in the prefix array.
- We will iterate first half (let’s say i) and find the range in the second half(let’s say j) such that prefix[j] should lie in the given range [prefix[i-1 + lower, prefix[i-1]+ upper].
- Count the number of pairs from the range.
- When the iteration of i is finished. then we will merge the two half into a single array.
Below is the implementation of the above approach:
#include <iostream>
#include <vector>
using namespace std;
// By Nitin Patel
// Function to merge two sorted subarrays of a given array
void merge(long long start, long long end,
vector<long long>& prefix)
{
long long n = end - start + 1;
long long mid = (start + end) / 2;
vector<long long> temp(n, 0);
long long i = start;
long long j = mid + 1;
long long k = 0;
// Merge the two subarrays in sorted order
while (i <= mid and j <= end) {
if (prefix[i] <= prefix[j]) {
temp[k++] = prefix[i++];
}
else {
temp[k++] = prefix[j++];
}
}
// Copy the remaining elements of the left subarray, if
// any
while (i <= mid) {
temp[k++] = prefix[i++];
}
// Copy the remaining elements of the right subarray, if
// any
while (j <= end) {
temp[k++] = prefix[j++];
}
// Copy the merged subarray back to the original array
for (int t = start; t <= end; t++) {
prefix[t] = temp[t - start];
}
}
// Recursive function to perform merge sort and count
// inversions
long long mergeSort(long long start, long long end,
vector<long long>& prefix, int lower,
int upper)
{
if (start == end) {
long long val = prefix[start];
// Check if the current element lies within the
// specified range
if (val >= (long long)lower
and val <= (long long)upper) {
return 1; // Count the element if it's within
// the range
}
else {
return 0; // Otherwise, don't count it
}
}
long long mid
= (start
+ ((end - start)
>> 1)); // Calculate the middle index
long long ans = 0; // Initialize the inversion count
// Recursively count inversions in the left and right
// halves
ans += mergeSort(start, mid, prefix, lower, upper);
ans += mergeSort(mid + 1, end, prefix, lower, upper);
// Count inversions involving elements from the left and
// right halves
long long i = start;
long long j = mid + 1;
long long k = mid + 1;
while (i <= mid) {
long long lowerbound = lower + prefix[i],
upperbound = upper + prefix[i];
// Find the index in the right half where elements
// are greater than the upper bound
while (j <= end and (prefix[j]) <= upperbound) {
j++;
}
// Find the index in the right half where elements
// are less than the lower bound
while (k <= end and (prefix[k]) < lowerbound) {
k++;
}
// Count the number of inversions involving elements
// from the left half and the right half
ans += (j - k);
i++;
}
// Merge the sorted halves
merge(start, end, prefix);
return ans;
}
// Function to count the number of elements within a given
// range in a sorted array
int getCount(vector<int>& nums, int n, int lower, int upper)
{
vector<long long> prefix(
n + 1, 0); // Create a prefix sum array
for (long long i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1]
+ nums[i - 1]; // Calculate the prefix
// sum at each index
}
return mergeSort(
1, n, prefix, lower,
upper); // Perform merge sort and count inversions
}
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.*;
public class CountElementsInRange {
// Function to merge two sorted subarrays of a given
// array
static void merge(long start, long end, long[] prefix)
{
long n = end - start + 1;
long mid = (start + end) / 2;
long[] temp = new long[(int)n];
long i = start;
long j = mid + 1;
long k = 0;
// Merge the two subarrays in sorted order
while (i <= mid && j <= end) {
if (prefix[(int)i] <= prefix[(int)j]) {
temp[(int)k++] = prefix[(int)i++];
}
else {
temp[(int)k++] = prefix[(int)j++];
}
}
// Copy the remaining elements of the left subarray
while (i <= mid) {
temp[(int)k++] = prefix[(int)i++];
}
// Copy the remaining elements of the right subarray
while (j <= end) {
temp[(int)k++] = prefix[(int)j++];
}
// Copy the merged subarray back to the original
// array
for (int t = 0; t < n; t++) {
prefix[(int)(start + t)] = temp[t];
}
}
// Recursive function to perform merge sort and count
// inversions
static long mergeSort(long start, long end,
long[] prefix, int lower,
int upper)
{
if (start == end) {
long val = prefix[(int)start];
// Check if the current element lies within the
// specified range
if (val >= lower && val <= upper) {
return 1; // Count the element if it's
// within the range
}
else {
return 0; // Otherwise, don't count it
}
}
long mid = start
+ ((end - start)
>> 1); // Calculate the middle index
long ans = 0; // Initialize the inversion count
// Recursively count inversions in the left and
// right halves
ans += mergeSort(start, mid, prefix, lower, upper);
ans += mergeSort(mid + 1, end, prefix, lower,
upper);
// Count inversions involving elements from the left
// and right halves
long i = start;
long j = mid + 1;
long k = mid + 1;
while (i <= mid) {
long lowerbound = lower + prefix[(int)i];
long upperbound = upper + prefix[(int)i];
// Find the index in the right half where
// elements are greater than the upper bound
while (j <= end
&& prefix[(int)j] <= upperbound) {
j++;
}
// Find the index in the right half where
// elements are less than the lower bound
while (k <= end
&& prefix[(int)k] < lowerbound) {
k++;
}
// Count the number of inversions involving
// elements from the left half and the right
// half
ans += (j - k);
i++;
}
// Merge the sorted halves
merge(start, end, prefix);
return ans;
}
// Function to count the number of elements within a
// given range in a sorted array
static int getCount(int[] nums, int n, int lower,
int upper)
{
long[] prefix
= new long[n + 1]; // Create a prefix sum array
for (int i = 1; i <= n; i++) {
prefix[i]
= prefix[i - 1]
+ nums[i - 1]; // Calculate the prefix sum
// at each index
}
return (int)mergeSort(
1, n, prefix, lower,
upper); // Perform merge sort and count
// inversions
}
public static void main(String[] args)
{
int n = 4;
int[] arr = { -2, 4, 1, -2 };
int lower = -4, upper = 1;
int answer = getCount(arr, n, lower, upper);
System.out.println(answer);
}
}
def merge(start, end, prefix):
n = end - start + 1
mid = (start + end) // 2
temp = [0] * n
i, j, k = start, mid + 1, 0
# Merge the two subarrays in sorted order
while i <= mid and j <= end:
if prefix[i] <= prefix[j]:
temp[k] = prefix[i]
k += 1
i += 1
else:
temp[k] = prefix[j]
k += 1
j += 1
# Copy the remaining elements of the left subarray, if any
while i <= mid:
temp[k] = prefix[i]
k += 1
i += 1
# Copy the remaining elements of the right subarray, if any
while j <= end:
temp[k] = prefix[j]
k += 1
j += 1
# Copy the merged subarray back to the original array
for t in range(start, end + 1):
prefix[t] = temp[t - start]
def merge_sort(start, end, prefix, lower, upper):
if start == end:
val = prefix[start]
# Check if the current element lies within the specified range
if lower <= val <= upper:
return 1 # Count the element if it's within the range
else:
return 0 # Otherwise, don't count it
mid = start + (end - start) // 2 # Calculate the middle index
ans = 0 # Initialize the inversion count
# Recursively count inversions in the left and right halves
ans += merge_sort(start, mid, prefix, lower, upper)
ans += merge_sort(mid + 1, end, prefix, lower, upper)
# Count inversions involving elements from the left and right halves
i, j, k = start, mid + 1, mid + 1
while i <= mid:
lowerbound = lower + prefix[i]
upperbound = upper + prefix[i]
# Find the index in the right half where elements are greater than the upper bound
while j <= end and prefix[j] <= upperbound:
j += 1
# Find the index in the right half where elements are less than the lower bound
while k <= end and prefix[k] < lowerbound:
k += 1
# Count the number of inversions involving elements from the left half and the right half
ans += (j - k)
i += 1
# Merge the sorted halves
merge(start, end, prefix)
return ans
def get_count(nums, lower, upper):
n = len(nums)
prefix = [0] * (n + 1) # Create a prefix sum array
for i in range(1, n + 1):
# Calculate the prefix sum at each index
prefix[i] = prefix[i - 1] + nums[i - 1]
# Perform merge sort and count inversions
return merge_sort(1, n, prefix, lower, upper)
def main():
n = 4
arr = [-2, 4, 1, -2]
lower, upper = -4, 1
answer = get_count(arr, lower, upper)
print(answer)
if __name__ == "__main__":
main()
// Function to merge two sorted subarrays of a given array
function merge(start, end, prefix) {
let n = end - start + 1;
let mid = Math.floor((start + end) / 2);
let temp = new Array(n).fill(0);
let i = start;
let j = mid + 1;
let k = 0;
// Merge the two subarrays in sorted order
while (i <= mid && j <= end) {
if (prefix[i] <= prefix[j]) {
temp[k++] = prefix[i++];
} else {
temp[k++] = prefix[j++];
}
}
// Copy the remaining elements of the left subarray, if any
while (i <= mid) {
temp[k++] = prefix[i++];
}
// Copy the remaining elements of the right subarray, if any
while (j <= end) {
temp[k++] = prefix[j++];
}
// Copy the merged subarray back to the original array
for (let t = start; t <= end; t++) {
prefix[t] = temp[t - start];
}
}
// Recursive function to perform merge sort and count inversions
function mergeSort(start, end, prefix, lower, upper) {
if (start === end) {
let val = prefix[start];
// Check if the current element lies within the specified range
if (val >= lower && val <= upper) {
return 1; // Count the element if it's within the range
} else {
return 0; // Otherwise, don't count it
}
}
let mid = start + Math.floor((end - start) / 2); // Calculate the middle index
let ans = 0; // Initialize the inversion count
// Recursively count inversions in the left and right halves
ans += mergeSort(start, mid, prefix, lower, upper);
ans += mergeSort(mid + 1, end, prefix, lower, upper);
// Count inversions involving elements from the left and right halves
let i = start;
let j = mid + 1;
let k = mid + 1;
while (i <= mid) {
let lowerbound = lower + prefix[i];
let upperbound = upper + prefix[i];
// Find the index in the right half where elements are greater than the upper bound
while (j <= end && prefix[j] <= upperbound) {
j++;
}
// Find the index in the right half where elements are less than the lower bound
while (k <= end && prefix[k] < lowerbound) {
k++;
}
// Count the number of inversions involving elements from the left half and the right half
ans += (j - k);
i++;
}
// Merge the sorted halves
merge(start, end, prefix);
return ans;
}
// Function to count the number of elements within a given range in a sorted array
function getCount(nums, lower, upper) {
let n = nums.length;
let prefix = new Array(n + 1).fill(0); // Create a prefix sum array
for (let i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + nums[i - 1]; // Calculate the prefix sum at each index
}
return mergeSort(1, n, prefix, lower, upper); // Perform merge sort and count inversions
}
// Main function
function main() {
let n = 4;
let arr = [-2, 4, 1, -2];
let lower = -4, upper = 1;
let answer = getCount(arr, lower, upper);
console.log(answer);
}
// Call the main function
main();
Output
5
Time Complexity: O(n log n)
Auxiliary Space: O(n)