This question is from the book The Algorithm Design Manual, 3-28.
The question is:
You have an unordered array X of n integers. Find the array M containing n elements where M_i is the product of all integers in X except for X_i. You may not use division and can use extra memory. (Hint: There exists solution faster than O(n^2).
Anybody has some great ideas?
O(n) solution:
Steps 1 and 2 can be computed in O(n) by using the subproducts computed in previous iterations.
[Of course, handle corner cases where the indices escape array bounds!]
Edit: I'm providing the complete solution below for clarity