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 <[email protected]>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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [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.
