@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 <srikar2...@gmail.com> 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 <learner....@gmail.com> 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 algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
