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