Well, instead of continuously storing the maximum product, you try to equate the product to k, if and when you do, you've found your sub array. To make it faster you can add another condition that when the product > k, stop and move to the next element (provided you've sorted the elements first)
I can't see a way to do this in O(n). Anyone? On Sep 30, 4:57 pm, abhishek singh <iiita2007...@gmail.com> wrote: > @ Minotauraus > * > * > *but here we are not going to find maximum product subarray, we are finding > here the subarray whose product is k. > * > correct me if i am wrong > > > > > > > > > > On Thu, Sep 30, 2010 at 9:35 PM, Minotauraus <anike...@gmail.com> wrote: > > I guess you could use Kadane's algo replacing addition with > > multiplication. > >http://en.wikipedia.org/wiki/Maximum_subarray_problem > > > On Sep 30, 8:08 am, Abhishek Kumar Singh <iiita2007...@gmail.com> > > wrote: > > > How will you find the subarray whose product is k in an array of > > > negative and positive numbers > > > > efficient algorithm is to be considered, it will be better if time > > > complexity is O(n) > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@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. > > -- > ABHISHEK KUMAR SINGH > BTECH (INFORMATION TECHNOLOGY) > IIIT ALLAHABAD > 9956640538 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
