@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 <[email protected]> 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 > <[email protected]>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 <[email protected]> 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 <[email protected]> wrote: >>> > @navin : hashMap can be used to do it in O(n) time. >>> > >>> > On 9/2/12, Carl Barton <[email protected]> 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 <[email protected]> >>> 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 >>> >>> <[email protected]>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 - [email protected] >>> >>>> >>> >>>> >>> >>>> -- >>> >>>> You received this message because you are subscribed to the Google >>> >>>> Groups >>> >>>> "Algorithm Geeks" group. >>> >>>> To post to this group, send email to [email protected]. >>> >>>> To unsubscribe from this group, send email to >>> >>>> [email protected]. >>> >>>> 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 [email protected]. >>> >>> To unsubscribe from this group, send email to >>> >>> [email protected]. >>> >>> 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 [email protected]. >>> >> To unsubscribe from this group, send email to >>> >> [email protected]. >>> >> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
