C Programming (interview)

Question

WAP where smallest subarrays with sum greater than x?

Say an array={1,5,6,2,45,17};

Now, x=60

Now we have to find smallest subarray which is greater than x

Comments

cant we do in this way that find the subarrays of Size 1, size 2 ,..... Size N an find the corresponding sum of each subarrays and then compare with each of subarray start from Size1  Subarray and so on..with the given value of X and if any smallest subarray sum would be greater than X then return that smallest subarray???????

---

@ srestha..I said general Idea. I could draw a zig-zag pattern curve, then it would be difficult the visualize. I got your point of discrete sum.

---

So, now how algorithm go?

why u think about decreasing curve? I am not getting that point

Answer 1

To solve a single program there are many algorithms.

Best solution always consider which has best complexity. this problem is a little bit tricky due to subarray otherwise nothing in this problem 3 step solution(sorting+comparison+print).

WHAT IS SUBARRAY(http://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/) 

1 soln. http://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/

Answer 2

we can apply sorting alogorithm like quick sort.

and choose the number contineously in the array upto the value reaches to greater then 60 and stop then

so its complexity wll O(nlogn)