Subarray with given sum

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

 

Example 1:

Input:
N = 5, S = 12
A[] = {1,2,3,7,5}
Output: 2 4
Explanation: The sum of elements 
from 2nd position to 4th position 
is 12.

 

Example 2:

Input:
N = 10, S = 15
A[] = {1,2,3,4,5,6,7,8,9,10}
Output: 1 5
Explanation: The sum of elements 
from 1st position to 5th position
is 15.

 

Your Task:
You don't need to read input or print anything. The task is to complete the function subarraySum() which takes arr, N and S as input parameters and returns a list containing the starting and ending positions of the first such occurring subarray from the left where sum equals to S. The two indexes in the list should be according to 1-based indexing. If no such subarray is found, return an array consisting only one element that is -1.

 

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

 

class Solution

{

    public:

    //Function to find a continuous sub-array which adds up to a given number.

    vector<int> subarraySum(int arr[], int n, int s)

    {

        // Your code here

        vector <int> res;

        int p1=0;

        int p2=0;

        //int sum=0;

        while(p2<n){

            int sum=0;

        for(int i=p1;i<=p2;i++){

            sum=sum+arr[i];

            

        }

        if(sum==s){

            res.push_back(p1+1);

            res.push_back(p2+1);

            return res;

        }

        else if(sum<s){

            p2++;

        }

        else p1++;

        }

        res.push_back(-1);

        return res;

        

}

};





i

Comments

Post a Comment

Popular posts from this blog

Sum of Even Numbers till N

Given a number N, print sum of all even numbers from 1 to N. #include<iostream> using namespace std; int main(){        /*  Read input as specified in the question. * Print output as specified in the question. */     int sum,n;     cin>>n;     sum=0;     for (int i=1;i<=n;i++){         if (i%2==0){             sum=sum+i;         }     }     cout<<sum;    } ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// #include<iostream> using namespace std; int main(){        /*  Read input as specified in the question. * Print output as specified in the question. */     int sum,n;     cin>>n;     sum=0;     for (int i=1;i<=n;i++){     ...
Read more

Find the Runner-Up Score!

  Given the participants' score sheet for your University Sports Day, you are required to find the runner-up score. You are given     scores. Store them in a list and find the score of the runner-up. Input Format The first line contains  . The second line contains an array     of   integers each separated by a space. Constraints Output Format Print the runner-up score. Sample Input 0 5 2 3 6 6 5 Sample Output 0 5 Explanation 0 Given list is  . The maximum score is  , second maximum is  . Hence, we print   as the runner-up score. ### OPTIMIZED ### from   collections   import   Counter if  __ name__  ==  '__main__' :      n  =  int ( input ())      arr  =  map ( int ,   input () . split ())           lis = list ( Counter ( arr ) . keys ())      lis . sort ()  ...
Read more

Print All Substrings

  For a given input string(str), write a function to print all the possible substrings. Substring A substring is a contiguous sequence of characters within a string. Example: "cod" is a substring of "coding". Whereas, "cdng" is not as the characters taken are not contiguous Input Format: The first and only line of input contains a string without any leading and trailing spaces. All the characters in the string would be in lower case. Output Format: Print the total number of substrings possible, where every substring is printed on a single line and hence the total number of output lines will be equal to the total number of substrings. Note: The order in which the substrings are printed, does not matter. Constraints: 0 <= N <= 10^6 Where N is the length of the input string. Time Limit: 1 second Sample Input 1: abc Sample Output 1: a ab abc b bc c  Sample Input 2: co Sample Output 2: c co o #include <iostream> #include <cstring> us...
Read more