@Srikar: You need to read what I said more carefully. An O(n log n) algorithm was proposed. I merely pointed out that it could not be optimal, since a trivial algorithm is O(n). I didn't say anything about the trivial algorithm being optimal or the solution to the problem.
Dave On Feb 2, 12:33 pm, Srikar <[email protected]> wrote: > hey dave! what do you mean naively clicking & O(n)? Can you explain the > exact algo? > > If you read the question properly, you should realize that it requires the > minimum clicks. > Naively clicking is not going to give you minimum clicks. > > > > On Wed, Feb 2, 2011 at 3:21 AM, Dave <[email protected]> wrote: > > @Srikar: Isn't it sort of silly to propose an O(n log n) algorithm > > when just naively clicking on the digits in order gives an O(n) > > algorithm? > > > Dave > > > On Feb 1, 12:04 pm, Srikar <[email protected]> wrote: > > > 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%2Bunsubscribe@googlegroups.com> > > <algogeeks%2Bunsubscribe@googlegroups.com> > > > > . > > > > For more options, visit this group at > > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - > > > > - Show quoted text - > > > -- > > 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%2Bunsubscribe@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- 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.
