- Take another sum array which contains sums of original array at each
index, here sum[0] = a[0]; sum[1] = a[0] + a[1]
;...sum[i]=a[0]+a[1]+...a[i];
- Traverse the sum array and search for duplicates.
ex: a[] = {1,2,-4,-3, 6 ,-3};
s[] = { 1,3,-1,-4,2,-1 };
In the sum array we have duplicates at 2nd index(i) and 5th index(j), so
in the original array pick the elements from 3(i+1) to 5(j) which are the
required elements , if there are no duplicates then u wont have sub array
with sum 0.
-Thanks
On Thu, Oct 20, 2011 at 1:54 AM, Ankur Garg <ankurga...@gmail.com> wrote:
> {You are given an unsorted array of integers. You have to find out the
> first sub array whose elements when added sum up to zero.
> eg:- int Array[] = {1,2,-4,-3, 6 ,-3.....}Here sub array is -3,6,-3 bcos
> adding all these sum to zero. A sub array can be of size 2 to whole length
> of the array. You can use extra space also for the same
>
>
> Brute Force will do it in O(n^2). Any better way
>
> I was thinking DP but couldnt find proper sub-problems and even if we do
> cudnt figure out lesser than O(n^2) :(
>
> Any suggestions?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
