Two passes. Initialize the result array with all 1's. Pass 1: Maintain the product until i-1 when processing element at i. The product would be 1 for the 0th element. For every i'th element of the result array, multiply it with the product (till the previous element).
Pass 2: Do the same but in the reverse direction. (Product initialized to 1 and its value being the product of all elements to the right of i'th element). On Sat, Oct 10, 2009 at 3:38 AM, Manisha <[email protected]> wrote: > > There is an array A[N] of N numbers. You have to compose an array > Output[N] such that Output[i] will be equal to multiplication of all > the elements of A[N] except A[i]. For example Output[0] will be > multiplication of A[1] to A[N-1] and Output[1] will be multiplication > of A[0] and from A[2] to A[N-1]. > > Solve it without division operator and in O(n). > > > > -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
