http://codepad.org/RrtoXLTX
On Sun, Aug 1, 2010 at 5:09 AM, Nikhil Jindal <fundoon...@yahoo.co.in>wrote: > Here's a possible O(n) soln: > > for all i, I calculate a[i].diff as number of zeroes - number of ones ones > from a[0] to a[i]. > > I do this in O(n). > > Also, I make a list of all the indexes that have a difference d(for all > possible d, which is n). > > Now, for it to be possible that the number of ones and number zeros between > two indices i and j are same, a[i].diff needs to be equal to a[j].diff > > Thus, for a particular difference d, in the list I take the first value of > the list and the last value and their diff gives me the maximum length of > string possible through diff d. > > Now find max by iterating thru all d's which is again O(n). > > Hence, time complexity: O(n) > Space: O(n) > > On Sun, Aug 1, 2010 at 12:33 PM, Ram Kumar <harrypotter....@gmail.com>wrote: > >> Given an array of 0s and 1s in any order, find the longest sequence >> that has equal number of 0s and 1s. >> >> 0 0 0 0 1 1 1 1 0 0 //array >> 0 1 2 3 4 5 6 7 8 9 //index >> ans1 (0,7) >> ans2 (1,8) >> ans3 (2,9) >> all having 4 0's and 4 1's >> >> -- >> Regards, >> Ramkumar.G >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > Please access the attached hyperlink for an important electronic > communications disclaimer: > http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php > > > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > <algogeeks%2bunsubscr...@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 algoge...@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.
