Data-Structure-Algorithms/SubarrayWithGivenSum.cpp at master · pallu2211/Data-Structure-Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;


 // } Driver Code Ends
class Solution
{
    public:
    //Function to find a continuous sub-array which adds up to a given number.

  //Solution part
    vector<int> subarraySum(int a[], int n, int s)
    {
        // Your code here
        int i=0,j=0,sum=0;
        vector<int> ans;
        while(j<n&&sum+a[j]<=s)
            sum+=a[j++];

         if(sum==s){
                ans.push_back(i+1);
                ans.push_back(j);
                return ans;
         }
        while(j<n){
            sum+=a[j];
            while(sum>s){
                sum-=a[i];
                i++;
            }
            if(sum==s){
                ans.push_back(i+1);
                ans.push_back(j+1);
                return ans;

            }
            j++;
        }
        ans.push_back(-1);
        return ans;
    }
  //Solution ends here
};

// { Driver Code Starts.

int main()
 {
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        long long s;
        cin>>n>>s;
        int arr[n];

        for(int i=0;i<n;i++)
            cin>>arr[i];
        Solution ob;
        vector<int>res;
        res = ob.subarraySum(arr, n, s);

        for(int i = 0;i<res.size();i++)
            cout<<res[i]<<" ";
        cout<<endl;

    }
	return 0;
}  // } Driver Code Ends