Google/fb/paypal

 Find subarray with given sum | Set 1 (Nonnegative Numbers)

  • Difficulty Level : Medium
  • Last Updated : 29 May, 2021

Given an unsorted array of nonnegative integers, find a continuous subarray which adds to a given number. 
Examples : 

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Ouptut: Sum found between indexes 2 and 4
Sum of elements between indices
2 and 4 is 20 + 3 + 10 = 33

Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Ouptut: Sum found between indexes 1 and 4
Sum of elements between indices
1 and 4 is 4 + 0 + 0 + 3 = 7

Input: arr[] = {1, 4}, sum = 0
Output: No subarray found
There is no subarray with 0 sum

There may be more than one subarrays with sum as the given sum. The following solutions print first such subarray. 



SOLUTION:

#include <iostream>

#include <bits/stdc++.h>

#include <climits>


using namespace std;




void display(int *arr, int n){


    for(int i=0;i<n;i++){


        cout<<arr[i];


    }


}






int main() {

    int arr[]={1,2,3,8};

    int n=sizeof(arr)/sizeof(int);

    int target=5;

    int i=0;

    int j=1;

    int count=0;

    int sum=0;

    while(i<n){

        while(j<n){

            sum=0;

            for(int k=i;k<=j;k++){

                sum=sum+arr[k];

            }

        if(sum<target){

            j++;

        }

        else if(sum>target){

            i++;

        }

        else if(sum==target){

            cout<<i+1<<" "<<j+1<<endl;

            count++;

            break;

        }

        if(count==1){

            break;

        }

        }

        if(count==1){

            //cout<<-1<<endl;

            break;

        }

        if(i==n-1){

            cout<<-1<<endl;

            break;

        }

    }

    

    

    



    return 0;


}

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