We can construct two arrays
P[i] = A[1] * A[2] * ... * A[i],
Q[i] = A[i] *A[i + 1] * ... *. A[n].
in linear time.
thus Ans[i] = P[i - 1] * Q[i + 1].
code like this
// A[1, ..., n] P[0] = Q[n + 1] = 1; for (int i = 1; i <= n; i++) { P[i] =
P[i - 1] * A[i]; Q[n - i + 1] = Q[n - i + 2] * A[n - i + 1]; } for (int i =
1; i <= n; i++) Ans[i] = P[i - 1] * Q[i + 1];
On Sun, Jun 6, 2010 at 3:42 AM, Raj N <[email protected]> wrote:
> Given an array arr[] of n integers, construct a Product Array prod[]
> (of same size) such that prod[i] is equal to the product of all the
> elements of arr[] except arr[i]. Solve it without division operator
> and in O(n).
>
> Can someone explain me the logic.
> Thanks!!
>
> --
> 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]<algogeeks%[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.
