An array puzzle

Question: 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]. Solve it without division operator and in O(n).

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].

Array 1: {4, 3, 2, 1, 2}

Output: {12, 16, 24, 48, 24}

Since the complexity required is O(n), the obvious O(n²) brute force solution is not good enough here. Since the brute force solution recomputes the multiplication each time again and again, we can avoid this by storing the results 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.

The above method requires only O(n) time but uses O(n) space. We have to trade memory for speed. Is there a better way? (i.e., runs in O(n) time but without extra space?)

Yes, actually the temporary array is not required. We can have two variables called left and right, each keeping track of the product of numbers multiplied from left->right and right->left. Could you see why this works without extra space?
Here is an implementation of the algorithm that does not require any extra space:-

#include<stdio.h>

void array_multiplication(int A[], int OUTPUT[], int n)
{
	// Initializing left and right
	int left = 1;
	int right = 1;
	
	// Initialize the output array
	int i = 0;
	for (i = 0; i < n; i++)
		OUTPUT[i] = 1;	

	for (i = 0; i < n; i++)
	{
		OUTPUT[i] *= left;
		OUTPUT[n - 1 - i] *= right;
		
		// The variable left stores the multiplication of
		// all elements on the left
		left *= A[i];
		
		// The variable right stores the multiplication of
		// all elements on the right
		right *= A[n - 1 - i];
	}
}

int main(void)
{
	
	int arr[] = {4, 3, 2, 1, 2};
	
	int OUTPUT[5] = {0};
	
	array_multiplication(arr, OUTPUT, 5);
	
	int i = 0;
	for(i=0; i<5; i++)
		printf("%d ",OUTPUT[i]);
	
	return 0;
}

Here is a running link of the above algorithm:- http://ideone.com/102tgS