Hi All, Algorithm :(as ankur suggested above) 1)Assume given array is a[]; 2)construct a temporary array of size a.length+1.Insert '0' as first element in temp(to simplify the edge conditional checks) 3)temp array contains sum of elements upto index(i) of that position. 4)Create a hashmap and traverse across the list.If the same number comes again,construct a list and add to the list. basicall hashmap contains position of contiguous elements which sum upto zero. 5)Now get all hashmap values(linkedlists):Linked list stores the positions which gives zero sum. for each linked list(if list size is greater than one) get the combaintions of two elements and call printarray method with start and end index.
I have implemented the above algorithm here(working java code). http://rajeevprasanna.blogspot.com/2011/07/contiguous-subarray-with-sum-zero.html Please let me know if any thing wrong.................... On Thu, Jul 21, 2011 at 1:12 PM, sagar pareek <sagarpar...@gmail.com> wrote: > thank you kamakshii................ :) > it is really helpful > > > On Thu, Jul 21, 2011 at 1:28 AM, Kamakshii Aggarwal <kamakshi...@gmail.com > > wrote: > >> use sum calculated in 2nd array as index for hashing..and index for second >> array as value of hashing; >> for example >> original array:20 , -9 , 3 , 1, 5 , 0, -6 , 9 >> array after addition:20 , 11,14,15,20,20,14,23 >> according to above example hashing will be like this >> k[20]=0; >> k{11]=1; >> k[14]=2; >> k[15]=3; >> again when now 20 comes so collision occurs as k[20] is already 1. >> therefore all the elements from index( k[20]+1) to 4(coz next 20 occurs at >> dis location) form the required string.. >> >> >> >> On Thu, Jul 21, 2011 at 12:43 AM, sagar pareek <sagarpar...@gmail.com>wrote: >> >>> how collision occur at 14 and 20 >>> actually i m not getting hash function >>> Thanks in advance >>> >>> On Thu, Jul 21, 2011 at 12:39 AM, Kamakshii Aggarwal < >>> kamakshi...@gmail.com> wrote: >>> >>>> @sagar: i read contiguous afterwards therefore i deleted my post... >>>> and for ankur's approach >>>> : >>>> original array:20 , -9 , 3 , 1, 5 , 0, -6 , 9 >>>> array after addition:20 , 11,14,15,20,20,14,23 >>>> >>>> now when u hash second array elements >>>> then u fill find collision at value 14 and 20 >>>> this means terms b/w 1st 14 and 2nd 14 adds t0 0.(1,5,0,-6)... >>>> is it clear now? >>>> >>>> >>>> >>>> On Thu, Jul 21, 2011 at 12:22 AM, Kamakshii Aggarwal < >>>> kamakshi...@gmail.com> wrote: >>>> >>>>> >>>>> a little mistake in ankur's solution >>>>> 20 , -9 , 3 , 1, 5 , 0, -6 , 9 >>>>> 20 , 11,14,15,20,20(instead of 0),14,23 >>>>> now if sum of two consecutive terms is same then this means a 0 >>>>> exists.and hence it can be printed as a subarray..else ankur's sol works >>>>> fine..:) >>>>> >>>>> >>>>> On Thu, Jul 21, 2011 at 12:06 AM, sagar pareek >>>>> <sagarpar...@gmail.com>wrote: >>>>> >>>>>> @ankur.... >>>>>> >>>>>> pls explain through an example by taking above problem..... >>>>>> >>>>>> >>>>>> On Wed, Jul 20, 2011 at 10:52 PM, SAMMM <somnath.nit...@gmail.com>wrote: >>>>>> >>>>>>> >>>>>>> >>>>>>> Nice solution dude .........!!!! Like that one .... >>>>>>> >>>>>>> -- >>>>>>> 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. >>>>>>> >>>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> **Regards >>>>>> SAGAR PAREEK >>>>>> COMPUTER SCIENCE AND ENGINEERING >>>>>> NIT ALLAHABAD >>>>>> >>>>>> -- >>>>>> 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. >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> Regards, >>>>> Kamakshi >>>>> kamakshi...@gmail.com >>>>> >>>> >>>> >>>> >>>> -- >>>> Regards, >>>> Kamakshi >>>> kamakshi...@gmail.com >>>> >>>> -- >>>> 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. >>>> >>> >>> >>> >>> -- >>> **Regards >>> SAGAR PAREEK >>> COMPUTER SCIENCE AND ENGINEERING >>> NIT ALLAHABAD >>> >>> -- >>> 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. >>> >> >> >> >> -- >> Regards, >> Kamakshi >> kamakshi...@gmail.com >> >> -- >> 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. >> > > > > -- > **Regards > SAGAR PAREEK > COMPUTER SCIENCE AND ENGINEERING > NIT ALLAHABAD > > -- > 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. > -- Thank You Rajeev Kumar -- 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.
