code will be something like minIdx[2N+1],maxIdx[2n+1]; all initialised to 1
for i = 0 to n-1 { if(a[i] == 0){ maxIdx[a[i]+n] = i; continue; } if(minIdx[a[i]+n] == -1){ minIdx[a[i]+n] = i; } else{ maxIdx[a[i]+n] = i; } } and finally compute the difference between all maxIdx and minIdx if maxIdx is not -1 On Fri, Jul 1, 2011 at 5:34 PM, abc abc <may.i.answ...@gmail.com> wrote: > @sunny very nice solution . > can you write the code for hashing part > > > On Fri, Jul 1, 2011 at 5:07 PM, Anantha Krishnan < > ananthakrishnan....@gmail.com> wrote: > >> here <http://www.careercup.com/question?id=3576940>. >> >> >> On Fri, Jul 1, 2011 at 4:38 PM, sunny agrawal <sunny816.i...@gmail.com>wrote: >> >>> String = 1 0 1 1 0 1 1 1. >>> 1. make the array = 1 -1 1 1 -1 1 1 1 >>> 2. after second operation >>> array = 1 0 1 2 1 2 3 4 >>> index = 0 1 2 3 4 5 6 7 >>> >>> >>> a[1] = 0 -> [0,1] is a solution >>> a[0] = a[2] = a[4] so (0,4],(0,2],(2,4] are also solutions >>> a[3] = a[5] (3,5] is also a solution. >>> >>> This Solution is O(n) in Both TC and SC >>> I have read this Question at many places but never seen a solution with >>> O(n) TC and O(1) space >>> where did you find these constraints ?? >>> >>> >>> On Fri, Jul 1, 2011 at 4:21 PM, Anantha Krishnan < >>> ananthakrishnan....@gmail.com> wrote: >>> >>>> Thanks. >>>> >>>> Can you plz explain for input 1 0 1 1 0 1 1 1. >>>> >>>> Also I want solution in O(n) TC and O(1) SC. >>>> >>>> Regards >>>> Anantha Krishnan >>>> >>>> >>>> On Fri, Jul 1, 2011 at 4:13 PM, sunny agrawal >>>> <sunny816.i...@gmail.com>wrote: >>>> >>>>> Take an array of size of the length of the string. >>>>> fill the array positions with one where string contains 1, and -1 where >>>>> it is 0 >>>>> >>>>> Now for each i (1,n-1) perform the following operation >>>>> a[i] = a[i-1] + a[i] >>>>> now a[i] will contains sum of values from a[0] to a[i] in original >>>>> array. >>>>> >>>>> Now only thing remains to find is two indexes in this array such that >>>>> a[i] = a[j] >>>>> where ever this condition is met ( i,j ] is a solution >>>>> >>>>> or if for some i a[i] = 0 in this case [0,i] will be a solution >>>>> >>>>> this can be done using hashing >>>>> hash the values in the array of size 2*n+1. as range of values is -n to >>>>> n and keep track of max interval. >>>>> >>>>> >>>>> >>>>> On Fri, Jul 1, 2011 at 3:22 PM, Anantha Krishnan < >>>>> ananthakrishnan....@gmail.com> wrote: >>>>> >>>>>> Given a string containing 0's and 1's. One would need to find the >>>>>> longest sub-string such that the count of 0's is equal to the count of >>>>>> 1's >>>>>> in the largest sub string. >>>>>> >>>>>> Regards >>>>>> Anantha Krishnan >>>>>> >>>>>> -- >>>>>> 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. >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> Sunny Aggrawal >>>>> B-Tech IV year,CSI >>>>> Indian Institute Of Technology,Roorkee >>>>> >>>>> -- >>>>> 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. >>>> >>> >>> >>> >>> -- >>> Sunny Aggrawal >>> B-Tech IV year,CSI >>> Indian Institute Of Technology,Roorkee >>> >>> -- >>> 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. > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.