Subarray with given sum

QUESTION

Given an unsorted array of non-negative integers, find a continuous subarray which adds to a given number.\n\nInput:\n\nThe 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 N 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.\n\nOutput:\n\nCorresponding to each test case, in a new line, print the starting and ending positions of first such occuring subarray if sum equals to subarray, else print -1.\n\nNote: Position of 1st element of the array should be considered as 1.\n\nExpected Time Complexity: O(n)\n\nConstraints:\n1<=T<=50\n1<=N<=100\n1<=an array element<= 200.

“TESTCASE_1”: “2\n5 12\n1 2 3 7 5\n10 15\n1 2 3 4 5 6 7 8 9 10\n###—###SEPERATOR—###—\n2 4\n1 5”, “TESTCASE_2”: “2\n5 12\n2 4 6 8 10\n10 15\n1 2 3 4 5 6 7 8 9 10\n###—###SEPERATOR—###—\n1 3\n1 5”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <bits/stdc++.h>
using namespace std;
int main() {
	int t,s,n,i,j,k,flag;
	cin>>t;
	while(t--){
	    cin>>n>>s;
	    int a[n+1],sum[n+1];
	    a[0]=0;
	    sum[0]=0;
	    flag=0;
	    for(i=1;i<=n;i++){
	        cin>>a[i];
	        sum[i]=sum[i-1]+a[i];
	    }
	    j=0;
	    for(i=1;i<=n;i++){
	        if(sum[i]-sum[j]==s){
	            cout<<j+1<<" "<<i<<endl;
	            flag=1;
	            break;
	        }
	        if(sum[i]-sum[j]>s){
	            j++;
	            i=j;
	        }
	    }
	    if(flag==0){
	        cout<<-1<<endl;
	    }
	}
	return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.