size of Smallest subarray with sum greater than a given value

Question

The original question is

Smallest subarray with sum greater than a given value Given an array of integers and a number x, find the smallest sub array with sum greater than the given value. at http://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/

but if the question was only to find the size of the smallest subarray, can we use divide and conquer method?

Algorithm: Size_of_min_subarray(1,n) =

min of { Size_of_min_subarray(1,n/2), Size_of_min_subarray(n/2,n),Size_of_array_containing mid_element(s) }

Size_of_array_containing_mid_element Is caluculated by:

Take the mid element(s) , initialise sum=mid element/sum of mid element and num_elements=1/2 based on n is odd or even .if sum<=given value,check if number to its right or left is greater.Add that greater element to the sum and increament num_elements. repeat until sum> given value.

Illustration:

1,4,45,6,0,19 and threshold=51

min_size=min{ min_size{1,4,45} , min_size{6,0,19} , min_containing_45and6 }

min_containing_45and6:

sum=mid elements/sum of mid elements=45+6=51<=51,num_elements=2. Since 4>0 add 4 to sum ,sum=55 and increament num_elements. num_elements=3.

min_size=min{ not possible , not possible , 3} =3.

Is this algorithm correct?And i think its complexity if O(logn),is that right?

Edit: i realized that the algo i am using to find Size_of_array_containin_mid_elemnts is wrong.can anyone suggest an algo for finding this value?

Answer 1

1. No sub-linear algorithm can solve this problem because it has to consider every array element at least once (worst case).

2. Your algorithm lacks the "base" step, i.e., Size_of_min_subarray(1,n) for small n (whatever "small" is).

3. The recurrence for your algorithm is F(n)=2*F(n/2)+G(n) where F(n) is the complexity of Size_of_min_subarray for size n and G(n) is the complexity of Size_of_array_containing_mid_element(n). Since G(n)~O(n), your algorithm is O(n).

Answer 2

1. If you're just trying to find the smallest sub array (if I'm reading this correctly) without any other parameters, wouldn't it always be whatever array of size 1?

2. The way I would approach this (could be faster ways) would be to have 2 "pointers" to indexes in the original array. You move one "pointer" through the array in a loop until the sum of values from the back "pointer" to the front "pointer" is greater than the value x. You can store that sub array or just the length fairly easily depending on what you want to do with the information. Once you find a viable solution, you move the back "pointer" forward until the sum between the two "pointers" is less than the threshold. Once that happens you move the front "pointer" forward again and repeat the steps above. You compare the lengths of the sub arrays and eventually come up with the right answer. The runtime is O(n^2) but it gets the correct answer.

The only issue with yours that I could see would be the fact that it could be possible to miss some cases. For example if you had {45, 1, 0, 4, 6, 19} (with the threshold still being 51) I think that by splitting the array/list the way you do you could miss a solution because of the split where 45 and 6 are on different halves of the list.

Please correct me if I'm wrong but I think what I have is close.

Answer 3

A very simple algorithm would be to get the max value for each possible sub arrays size until you have a sub array with a sum greater than the given value.

So if you have an array of 6 elements you start checking if there is an sub array of size 1 bigger or equal than then given value (in other word, a single value bigger than the given value). If not check with sub arrays of size 2. If not check with sub arrays of size 3.. and it goes on...

Worst case is you need to sum all the array values to reach the given value.