Subarray With The Given Sum - Optimal Solution

Prashant | Thu, 04 Jun, 2020 | 562

Subarray with the given sum - optimal solution using sliding window

This subarray question is widely asked in many placements and interview questions, as you may not find an optimal solution and end up having time limit error.

Nothing to worry about we always bring you best optimal solution to help you out in acing every test and interviews.

Question Description 

Given an unsorted array of size N of non-negative integers, find a continuous sub-array which adds to a given number S.

Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. The first line of each test case is and S, where N is the size of array and S is the sum. The second line of each test case contains N space separated integers denoting the array elements.

Output:
For each testcase, in a new line, print the starting and ending positions(1 indexing) of first such occuring subarray from the left if sum equals to subarray, else print -1.

Constraints:
1 <= T <= 100
1 <= N <= 107
1 <= Ai <= 1010

Example:
Input:
2
5 12
1 2 3 7 5
10 15
1 2 3 4 5 6 7 8 9 10
Output:
2 4
1 5

Explanation :
Testcase1: sum of elements from 2nd position to 4th position is 12
Testcase2: sum of elements from 1st position to 5th position is 15

See visual before 

 

Solution for the program 

#include<bits/stdc++.h>
using namespace std;
int main()
 {
	int t;cin>>t;
	while(t--){
	    int n,sum=0,s;cin>>n>>s;
	    int arr[n];
	    for(int i=0;i<n;i++){
	        cin>>arr[i];
	    }
	    
	    int header=0,flag=0;
	    for(int i=0;i<n;i++){
	        sum+=arr[i];
	        while(sum>s){
	            sum-=arr[header];
	            header++;
	        }
	        if(sum==s){
	            cout<<header+1<<" "<<i+1<<endl;
	            flag=1;
	            break;
	        }
	    }
	    if(flag==0)
	    cout<<"-1\n";
	    
	    
	}
	return 0;
}

 

0 comments
Leave a comment