hi, I suppose this could be solved in O(n) time if we use hash table. although the space complexity will increase
Thanks and regards, Gajendra Dadheech On Thu, Feb 3, 2011 at 12:47 AM, Dave <[email protected]> wrote: > @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%[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%[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]<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.
