@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.
