O/P should be 00111010 and sub array is exclusive of start index, inclusive of end index.
Nice solution On Thu, Sep 29, 2011 at 11:58 AM, UTKARSH SRIVASTAV <[email protected] > wrote: > @Amol +1 > > On Thu, Sep 29, 2011 at 11:52 AM, Amol Sharma <[email protected]>wrote: > >> given array- >> 1 0 0 1 1 1 0 1 0 1 >> for our convenience lets replace 0 by -1 >> array becomes >> 1 -1 -1 1 1 1 -1 1 -1 1 >> >> take another array count which which represents the sum till that index >> sum array becomes >> 1 0 -1 0 1 2 1 2 1 2 //count array >> >> now make an important observation that if a number repeats in the count >> array then between that two indexes equal number of zeros and ones have been >> added....... >> >> now take 2 arrays of size 2n+1 and index them from -n to n.....lets call >> them array a_front and a_back........the idea behind indexing is that the >> possible value of sum varies from -n(all 0's) to +n(all 1's) >> >> >> for *a_front* >> traverse the count array from front and for each number update index of >> it's first occurrence in the a_front array >> in this case...a_front[1]=0,a_front[0]=1,a_front[-1]=2,a_front[2]=6...only >> these four entries will be updated in the a_front array >> >> for *a_back* >> traverse the count array from back and for each number update index of >> it's last occurrence in the a_back array >> in this case...a_back[2]=9,a_back[1]=8,a_back[0]=3,a_back[-1]=2..only >> these four entries will be updated in the a_back array >> >> now traverse both a_front and a_back simultaneously >> max(a_back[i]-a_front[i]) will indicate the maximum subarray with equal >> zeros and ones. >> >> Hope this helps !! >> >> >> >> -- >> >> >> Amol Sharma >> Third Year Student >> Computer Science and Engineering >> MNNIT Allahabad >> <http://gplus.to/amolsharma99> >> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://youtube.com/amolsharma99> >> >> >> >> >> >> On Thu, Sep 29, 2011 at 10:39 AM, kartik sachan >> <[email protected]>wrote: >> >>> Given a binary array ( array containing only 0s and 1s ). You have to >>> print the sub-array with >>> maximum number of equal 1s and 0s. >>> INPUT OUTPUT >>> 1001110101 0011101 >>> >>> >>> complex-O(n) >>> >>> -- >>> >>> *WITH REGARDS,* >>> * >>> * >>> *KARTIK SACHAN* >>> >>> *B.TECH 3rd YEAR* >>> *COMPUTER SCIENCE AND ENGINEERING* >>> *NIT ALLAHABAD* >>> >>> -- >>> 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. >> > > > > -- > *UTKARSH SRIVASTAV > CSE-3 > B-Tech 3rd Year > @MNNIT ALLAHABAD* > > > -- > 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.
