Q:

Given an unsorted array A of size N of non-negative integers, find a continuous sub-array which adds to the given number

0

Finding subarray with given sum

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

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

    1. A in the input array, n is the length of the array & s in the given sum.
    2. Initialize vector b. (for storing indexes of subarray)
    3. Initialize a variable cur_sum=0
    4. for i=0:n-1
	set cur_sum=A[i]
	for j=i+1:n-1
		add A[j] to cur_sum
		if(cur_sum==s)
			i is the starting index of subarray found
			j is the end index of subarray found
			print elements between indexes i & j
            (including i & j) & return to main
		end if
		if cur_sum become greater than s then break loop
	end for
end for
  1. If control comes out of the loop that means so such subarray exists, thus print "no subarray found".

C++ implementation to find subarray with given sum

#include <bits/stdc++.h>
using namespace std;

vector<int> find(vector<int> a,int n,int s){
	vector<int> b; //output vector
	int cur_sum=0;
	for(int i=0;i<n;i++){
		cur_sum=a[i];//cur_suming element
		for(int j=i+1;j<n;j++){
			//add next element contigeously 
			cur_sum=cur_sum+a[j]; 
			// if current sum  is eaqual to the sum value
			if(cur_sum==s){ 
				//insert array index of the cur_sum element in sub array
				b.push_back(i); 
				//insert array index of the last element in sub array
				b.push_back(j); 
				return b;
			}
			if(cur_sum>s)
				break;
		}
	}
	// if no such sub array exists
	b.push_back(-1); 
	return b;
} 

int main() {
	//code
	int s,n,no;
	cout<<"enter array length & Sum respectively"<<endl;
	scanf("%d%d",&n,&s);

	vector<int> a; //input array

	cout<<"enter array elements........"<<endl;
	for(int j=0;j<n;j++){
		scanf("%d",&no);
		a.push_back(no); //inserting array elements
	}

	vector<int> b=find(a,n,s);
	if(b[0]==-1)
		printf("subarray not found");
	else{
		cout<<"Subarray is: ";
		for(int i=b[0];i<=b[1];i++)
			cout<<a[i]<<" ";
		cout<<endl;
	}	    
	return 0;
}

Output

First run:
enter array length & Sum respectively
8
20 
enter array elements........ 
4
2
10 
3
-3 
10 
5
5
Subarray is: 10 3 -3 10 


Second run:
enter array length & Sum respectively
6
15 
enter array elements........ 
5
1
-6 
7
7
3
subarray not found

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now