nice idea..
On Oct 20, 11:04 am, SUMANTH M <sumanth.n...@gmail.com> wrote:
> - 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.
