Task: Find the continuous sub-array, from given an array of size N non negative integers, which sum is equal to given S.
Example:
Input:
1
5 12
1 2 3 7 5
Output:
2 4 // starting and ending positions of sub-array.
Here is the code:
Program in C++:
- #include<iostream>
- using namespace std;
- int main()
- {
- int t;
- cin>>t;
- while(t--)
- {
- int n,s;
- cin>>n>>s;
- int a[n];
- for(int i=0;i<n;i++)
- {
- cin>>a[i];
- }
- // Implementaion of Logic
- int sas=0,i=0,c=0;
- for(int j=0;j<n;j++)
- {
- if(sas+a[j]<=s)
- {
- sas+=a[j];
- }
- else
- {
- sas+=a[j];
- while(sas>s)
- {
- sas-=a[i];
- i++;
- }
- }
- if(sas==s)
- {
- cout<<i+1<<" "<<j+1<<endl;
- c=1;
- break;
- }
- }
- if(c==0) cout<<-1<<endl;
- }
- return 0;
- }
Here is the Video: