Efficiently multiply (n-1) elements of an array [duplicate]

Question

Possible Duplicate:
Interview Q: given an array of numbers, return array of products of all other numbers (no division)

I have two arrays inputArray and resultArray having n elements each.
The task is that the nth element in resultArray should have the multiplication of all elements in inputArray except the nth element of inputArray (n-1 elements in all).
eg. inputArray={1,2,3,4}
then resultArray={24,12,8,6}
This is easy...

for(i = 0; i < n; i++)
  for(j = 0; j < n; j++)
    if(i != j) resultArray[i] *= inputArray[j];

But the problem is that the complexity shouldn't exceed O(n)
Also we are not allowed to use division.
How do I solve this?

Answer 1

Without spoiling too much, you should try and use two variables to store the result of the multiplications: both the cumulative result of the multiplications on the left of the i'th element and on the right of the i'th element.

Answer 2

You can use a DP approach, something like this:

vector<int> products(const vector<int>& input) {
    int N = input.size();
    vector<int> partial(N+1); // partial[i] = input[0]...input[i-1]. partial[0] = 1
    partial[0] = 1;
    for (int i = 0; i < N; ++i) partial[i+1] = input[i]*partial[i];
    vector<int> ans(N);
    int current = 1;
    for (int i = N-1; i >= 0; --i) {
        // current is equal to input[i+1]...input[N-1]
        ans[i] = partial[i]*current;
        current *= input[i];
    }
    return ans;
}

One possible usage for this approach is when you are working with things you cannot divide by (think of this same problem with matrices, for instance).

I did this solution using STL vector, but of course the code can be easily "translated" to work with C arrays.