On Oct 10, 9:12 pm, Ramaswamy R <ramaswam...@gmail.com> wrote:
> 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 <pgo...@gmail.com> 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
Two passes won't be necessary ! You can do it in a single pass, the
mater of fact is that the logic is quite similar to yours.
Initialize the result array to 1.
Take two variables:
left = 1; // l is the product of the values of the left side of an
index in x
right = 1; // r is the product of the values of the right side of an
index in x
Then do this:
for (i=0 ; i<n ; i++)
{
res[i] = res[i]*left ;
res[n-i-1] = res[n-i-1]*right;
left *= A[i];
right *= A[n-i-1];
}
The res is now the required array :-)
The C-code implementing my algo :http://codepad.org/nLWmNtDy
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
