Multiplication of numbers

Q: 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).

A: {4, 3, 2, 1, 2}
OUTPUT: {12, 16, 24, 48, 24}

Since we should not use, division operator, Brute force approach would be O(n^2)

Other approach is by storing the result temporarily in an array.

Let’s define array B where element B[i] = multiplication of numbers from A[0] to A[i]. For example, if A = {4, 3, 2, 1, 2}, then B = {4, 12, 24, 24, 48}. Then, we scan the array A from right to left, and have a temporary variable called product which stores the multiplication from right to left so far. Calculating OUTPUT[i] is straight forward, as OUTPUT[i] = B[i-1] * product.

Above approach requires O( n ) time and also O( n ) space.

We can actually avoid the temporary array. We can have two variables called left and right, each keeping track of the product of numbers multiplied from left->right and right->left.