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.
