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.

Powered By
CHP Adblock Detector Plugin | Codehelppro