@Dave: Very good solution.. I had thought an idea of using separate arrays to store next and previous products. And multiplying the elements of the 2 arrays to give B. The solution given by you satisfies ALL constraints inplace :)
@sameer: Your solution is not O(1) in space dude..Dave's solution is good. On Jun 26, 9:47 pm, Ashish Goel <[email protected]> wrote: > this is goog question > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > > > > > > On Sun, Jun 26, 2011 at 10:04 PM, Dave <[email protected]> wrote: > > @Ross: This satisfies your constraints... > > > B[0] = 1; > > for( i = 1 ; i < N ; ++i ) > > B[i] = B[i-1] * A[i-1]; > > int x = 1; > > for( i = N-1 ; i > 0 ; --i ) > > { > > x *= A[i]; > > B[i-1] *= x; > > } > > > Dave > > > On Jun 26, 11:08 am, ross <[email protected]> wrote: > > > Given an array A , of N integers ( In no particular order), fill up an > > > auxilary array B such that B[i] contains the product of > > > all elements in A other than A[i]. > > > Constraints: > > > O(n) Time, > > > Can this be done with O(1) space? > > > Division is *not* allowed . > > > > eg: A 1 2 3 4 5 > > > B 120 60 40 30 24 > > > -- > > 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. -- 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.
