@atul: what if n-1 contiguous 0's are there?? Can't we have some mechanism in hash such that it will avoid O(n^2) ??
On Mon, Sep 3, 2012 at 12:29 AM, atul anand <atul.87fri...@gmail.com> wrote: > @navin : this case can be avoided by checking input array first , if > it contain all zero or not....which will be O(n). > > > On 9/2/12, Navin Kumar <algorithm.i...@gmail.com> wrote: > > @atul : suppose if all element of input array is zero then i think > hashing > > will also produce n^2 output. so worst case time complexity would be > > O(n^2). > > > > On Sun, Sep 2, 2012 at 9:18 PM, Carl Barton > > <odysseus.ulys...@gmail.com>wrote: > > > >> No you're correct. I was doubting it would work :P > >> > >> For hashing you would need perfect hashing to ensure O(n) wouldn't you? > >> > >> > >> On 2 September 2012 23:21, atul anand <atul.87fri...@gmail.com> wrote: > >> > >>> @carl : if it would work only for entirely positive integers , then i > >>> aux[] array created will never contain 0 or repeated elements... > >>> correct me if i am wrong... > >>> > >>> On 9/2/12, atul anand <atul.87fri...@gmail.com> wrote: > >>> > @navin : hashMap can be used to do it in O(n) time. > >>> > > >>> > On 9/2/12, Carl Barton <odysseus.ulys...@gmail.com> wrote: > >>> >> Your approach sounds like the optimal (and linear) algorithm for the > >>> >> submass finding problem. But if I recall correctly that only works > in > >>> >> linear time if the input is entirely positive integers? > >>> >> Maybe I'm being stupid but wont checking that array be quadratic? > >>> >> > >>> >> On 2 September 2012 20:02, Navin Kumar <algorithm.i...@gmail.com> > >>> wrote: > >>> >> > >>> >>> @pradip: Finding same element in temp array is little bit tricky. > >>> >>> For > >>> >>> displaying item from i+1 to j , you have to make sure that there is > >>> >>> equal > >>> >>> element at i and j index in temp array. How will you ensure it in > >>> >>> O(n) > >>> >>> time? > >>> >>> > >>> >>> > >>> >>> On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra > >>> >>> <pradam.prad...@gmail.com>wrote: > >>> >>> > >>> >>>> This algorithm is *O(n)*. > >>> >>>> > >>> >>>> Given an int[] input array, you can create an int[] tmp array > where > >>> >>>> tmp[i] > >>> >>>> = tmp[i - 1] + input[i]; Each element of tmp will store the sum of > >>> the > >>> >>>> input up to that element. > >>> >>>> > >>> >>>> Now if you check tmp, you'll notice that there might be values > that > >>> are > >>> >>>> equal to each other. Let's say that this values are at indexes j > an > >>> >>>> k > >>> >>>> with j < k, then the sum of the input till j is equal to the sum > >>> tillk > >>> >>>> and > >>> >>>> this means that the sum of the portion of the array between j and > k > >>> is > >>> >>>> 0! Specifically the 0 sum subarray will be from index j + 1 to k. > >>> >>>> > >>> >>>> - NOTE: if j + 1 == k, then k is 0 and that's it! ;) > >>> >>>> - NOTE: The algorithm should consider a virtual tmp[-1] = 0; > >>> >>>> > >>> >>>> Correct me if i am wrong Thanx > >>> >>>> > >>> >>>> -- > >>> >>>> Pradeep Kumar Mishra > >>> >>>> IIIT Allahabad > >>> >>>> B. Tech 3rd Year ( IT ) > >>> >>>> Another Mail - prad...@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. > >>> >>>> > >>> >>> > >>> >>> -- > >>> >>> 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. > >>> >> > >>> >> > >>> > > >>> > >>> -- > >>> 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. > >> > > > > -- > > 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. > > -- 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.
