Could I sort it? Oh you mentioned that the original array could be destroyed.
In that case, 1) Sort the array - O(nlogn) 2) loop through the array. if contiguous elements are same remove all of them in one click else remove only that element. - O(n) Time - O(nlogn) space - O(1) On Tue, Feb 1, 2011 at 7:23 PM, snehal jain <[email protected]> wrote: > You are given an array A of length N. You have to destroy it, given > that you have the power to remove any continuous chunk of same numbers > with 1 click. Thus the order in which you remove chunk matters. For > example given {1, 2, 3, 1} normally it will take you 4 clicks to > remove but if you first remove 2 making array {1, 3, 1} then 3 making > it {1, 1} and then you can remove this continuous chunk of similar > number in one click, thus completing the task in 3 clicks. How to find > minimum number of clicks required? Another example is {1, 2, 3, 2, 1} > which can be destroyed in 3 clicks > > -- > 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. > > -- 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.
