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 <rajn...@gmail.com> 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 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. > > -- 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.