yes but for largest interval we need only one index :) greater of i or j On Fri, Jul 1, 2011 at 6:01 PM, Dumanshu <duman...@gmail.com> wrote:
> @sunny: if a[i]==0 then 0,i is the solution > suppose a[i]==a[j] ==0 now 0,i and 0,j is the solution. is i,j also > the solution?? > > On Jul 1, 4:08 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- Hide quoted text - > > > > - Show quoted text - > > -- > 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.
