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 <dave_and_da...@juno.com> 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 <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%2bunsubscr...@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<algogeeks%2bunsubscr...@googlegroups.com>
> .
> 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 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.
