I have one more approach in mind where it requires T(n) = O(n) and
O(1) space complexity. here it goes:
1) Start traversing the array.
2)Store the location when 0 and 1 both appears for the first time in
some variable.
3)Similarly store the location of 0 and 1 when both appears for the
last time in the string.
4) Keep a count of the number of times 0 and 1 appear in the whole
string.
4)Now the observation is whichever has lower count will decide the
longest sub-string.
5) Say 0 has a lower count, then observe the (difference between the
first, lets name it as fi_0 and the last location, lets say this is
la_0 of 0) with that of total count of 0s ,lets name it as co_0in the
string.
6) If (la_0 - fi_0 + 1) == 2*co_0
then the final substring lies within this range of f_0 to l_0
because the string contains only 0s and 1s so the rest of the numbers
apart from 0 are 1 and equal in number too.
else If(la_0 - fi_0 + 1) < 2*co_0
it means that number of 1s are less in this range, so lets take
some more 1s from the rest of the string and finalize the string.
else
it means that number of 1s are more in this range, we need to
reduce some zeros in this case, here start from any end say la_0 and
go backwards. While traversing back you will encounter both 0s and 1s,
so continue to traverse back until you do not obtain the balance and
when achieved then note the final length sayl1. Similarly follow the
same process from fi_0 and note length as l2. Compare l1 and l2 and
accordingly decide the final substring.
Done.....
Yogesh Garg,
Computer Engineering,
Netaji Subhas Institute of Technology, New Delhi
On Jul 1, 4:08 am, sunny agrawal <[email protected]> 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 <
>
>
>
>
>
>
>
>
>
> [email protected]> 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
> > <[email protected]>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 <
> >> [email protected]> 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 [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.
>
> >> --
> >> 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 [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.
>
> --
> 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 [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.
