Find continuous subarray/subsequence with given sum

- 


void subarr(int arr[],int n, int sum){
    map<int,int> map;    int curr_sum=0;    for(int i=0;i<n;i++){
        curr_sum+=arr[i];        if(curr_sum==sum){
            cout<<"Sum found between "<<0<<" and "<<i<<endl;            return;        }
        if(map.find(curr_sum-sum)!=map.end()){
            cout<<"Sum found between "<<map[curr_sum-sum]+1<<" and "<<i<<endl;            return;        }
        map[curr_sum]=i;    }
    cout<<"No Subarray found "<<endl;}










































Comments











Post a Comment



















Popular posts from this blog









Efficient Method to Calculate Power






-















 For a^b=(a X a X a X a.....X a)   eg. for a=3, b=10  This can be written as 3^10 = (3^5)^2  Using this logic we can implement   long long power(long long a, long long b){      long long res=1;      while(b>0){           if(b%2==1)//Odd Number{               res*=a;           }           a*=a;           b/=2;      }      return res;  }   








Read more











Efficient way to print factors of a number






-















 Factors of a number n can be defined as the set of numbers which are divisible by n. eg. n=24 factors={1,2,3,4,6,8,12,24}; On native approach this can be done in time complexity O(n), but on efficient approach this can be done in O(sqrt(n));   For n=100;  its factors are 1,2,4,5,10,20,25,50,100;  If noticed carefully, it exists in pair, whose product form the number n;  (1,100),(2,50),(4,25),(5,20),(10,10), we can see an exception for middle element 10, for odd numbers of factors.   Similarly for n=24;  factors: 1,2,3,4,6,8,12, 24  pairs: (1,24),(2,12),(3,8),(4,6)   Further we can notice few more points:   1.  If (a,b) is a pair, 1<=a<=sqrt(n)  2. If (a,b) is a pair, b=n/a; as a*b=n   Therefore progmatically,   void Facotrs(int n){      for(int i=1;i<=sqrt(n);i++){          if(n/i=i)//OR i*i==n , for equal divisor element         {             print(i);          }    ...








Read more