Find all subarrays with sum in the given range
Given an unsorted array of size, N. Find subarrays that add to a sum in the given range L-R.
Examples:
Input: arr[] = {2, 3, 5, 8}, L = 4, R = 13
Output: The indexes of subarrays are {0, 1}, {0, 2}, {1, 2}, {2, 2}, {2, 3}, {3, 3}Input: arr[] = {1, 4, 6}, L = 3, R = 8
Output: The indexes of subarrays are {0, 1}, {1, 1}, {2, 2}
Naive approach: Follow the given steps to solve the problem using this approach:
- Generate every possible subarray using two loops
- If the sum of that subarray lies in the range [L, R], then push the starting and ending index into the answer array
- Print the subarrays
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find subarrays with sum // in the given range void findSubarrays(vector< int > &arr, vector<pair< int , int >> &ans, int L, int R) { int N = arr.size(); for ( int i=0; i<N; i++) { int sum = 0; for ( int j=i; j<N; j++) { sum += arr[j]; // If the sum is in the range then // insert it into the answer if (sum >= L && sum <= R) ans.push_back({i, j}); } } } void printSubArrays(vector<pair< int , int >> &ans) { int size = ans.size(); for ( int i=0; i<size; i++) cout<<ans[i].first<< " " <<ans[i].second<<endl; } // Driver Code int main() { vector< int > arr = {2, 3, 5, 8}; int L = 4, R = 13; vector<pair< int , int >> ans; // Function call findSubarrays(arr, ans, L, R); printSubArrays(ans); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to find subarrays with sum // in the given range static void findSubarrays( int arr[], int N, int L, int R) { for ( int i = 0 ; i < N; i++) { int sum = 0 ; for ( int j = i; j < N; j++) { sum += arr[j]; // If the sum is in the range then // insert it into the answer if (sum >= L && sum <= R) System.out.println(i + " " + j); } } } public static void main(String[] args) { int N = 4 ; int arr[] = { 2 , 3 , 5 , 8 }; int L = 4 , R = 13 ; // Function call findSubarrays(arr, N, L, R); } } // This code is contributed by mudit148. |
Python3
# Python3 program for the above approach # Function to find subarrays with sums # in the given range def findSubarrays(arr, N, L, R): for i in range (N): sums = 0 ; for j in range (i, N): sums + = arr[j]; # If the sums is in the range then # insert it into the answer if (sums > = L and sums < = R): print (i, j); N = 4 ; arr = [ 2 , 3 , 5 , 8 ]; L = 4 R = 13 ; # Function call findSubarrays(arr, N, L, R); # This code is contributed by phasing17. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find subarrays with sum // in the given range static void findSubarrays( int [] arr, int N, int L, int R) { for ( int i = 0; i < N; i++) { int sum = 0; for ( int j = i; j < N; j++) { sum += arr[j]; // If the sum is in the range then // insert it into the answer if (sum >= L && sum <= R) Console.WriteLine(i + " " + j); } } } public static void Main( string [] args) { int N = 4; int [] arr = { 2, 3, 5, 8 }; int L = 4, R = 13; // Function call findSubarrays(arr, N, L, R); } } // This code is contributed by phasing17. |
Javascript
// JS program for the above approach // Function to find subarrays with sum // in the given range function findSubarrays(arr, N, L, R) { for (let i = 0; i < N; i++) { let sum = 0; for (let j = i; j < N; j++) { sum += arr[j]; // If the sum is in the range then // insert it into the answer if (sum >= L && sum <= R) console.log(i + " " + j); } } } let N = 4; let arr = [ 2, 3, 5, 8 ]; let L = 4, R = 13; // Function call findSubarrays(arr, N, L, R); // This code is contributed by phasing17. |
Output
0 1 0 2 1 2 2 2 2 3 3 3
Time complexity: O(N2)
Auxiliary Space: O(N2)