CareerCup

int index = 0;
		for (int i = 0; i < a.length;) {
			while (sum > k && index < i) {
				sum = sum - a[index];
				index++;
			}
			if (sum == k) {
				for (int k = index; k < i; k++) {
					System.out.print("-" + a[k]);
				}
			}
			sum = sum + a[i];
			i++;
		}

	}

if we are allowed to use space of O(n), then its time comp O(n).
create aux an array with a[i]=sum of elements upto i in the given array.
now its a simple problem of x-y=k; which can solved in O(n). (aux array is sorted).

aux is sorted????....how cn u say that because given array is unsorted and may also contain negative integer anywhere in it..

@saraf
if array contain negative numbers too,
then construct a bst with each node containing parent pointer and an other pointer
which points to the middle of the path from ancestor of node to the node.
Hence you can construct the bst in O(n).
now proceed to the problem from there.

@saraf
if array contain negative numbers too,
then construct a bst with each node containing parent pointer and an other pointer
which points to the middle of the path from ancestor of node to the node.
Hence you can construct the bst in O(n).
now proceed to the problem from there.

hashMap is d solution

it is unsorted array and we need a sub array of it. So I think it is not allowed to create BST, because we are changing the order of the array.
for example: an array of {1,2,3,7,8,4,5} and k=12 then the sub array would be {2,3,7} and {8,4}
if this is the case then the time complexity in worst case is o(n^2).
I couldn't find better solution.

# include<stdio.h>

int main()

{


int arr[]= {1,3,1,3,4,2,6,6,7,10};

int i,j,sum,maxsum,len;
printf("\n entere the sum");
scanf("\n %d", &sum);

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

for(i=0;i<len;i++)
{maxsum=0;
for(j=i;j<len;j++)
{
maxsum=maxsum+arr[j];

if(maxsum==sum)
{
printf("\n sum found at %d and between %d and %d", maxsum,i,j);

}
}

}

}

/*
find the sub array of sum K from the the given unsorted array
*/
#include <iostream>
#include <conio.h>
#include <array>
using namespace std;
void getSubArray(int arr[],int arraySize,int * start, int * end, int desiredSum){
	int sum = 0;
	cout<<"initial values of start and end pointer elements: "<<*start<<" "<<*end<<endl;
	
	if(arraySize==1){return;}

	start = arr;
	end = arr+1;
	int count = 1;	
	
	sum = sum + *start + *end;
	
	
	while(count < arraySize){		
		
		if(desiredSum == sum){	
			cout<<"Final subarray is: ";
			while(start<=end){
				cout<<*start<<" ";
				start++;
			}
			return;
		}
		if(sum<desiredSum){
			end++;
			sum += *end; 
		}
		if(sum>desiredSum){
			sum -= *start;
			start++;
		}
		count++;
	}
	cout<<"No sub array found with desired sum"<<endl;
	
}
int main(){
	int arr[5]={2,2,4,1,5};
	int * start= arr;
	int * end= arr + 1;
	int arraySize = sizeof(arr)/sizeof(*arr);	
	
	getSubArray(arr,arraySize,start,end,6);	
	getch();
return 0;
}

o/p:
initial values of start and end pointer elements: 2 2
Final subarray is: 2 4

Th questions address contiguous sequence or sequence in any order? What is meant by sub array?

knapsack is the solution...

We can use DP in order to find the subarray

if(a[n] > Sum)
Subarray(a,n-1,Sum)
else
Subarray(a,n-1, sum-a[n]) || Subarray(a,n-1, sum)

If the subarray need not to be contiguous then it is a standard subset sum problem.