Given an array A of n numbers you are asked to output a new

Given an array A of n numbers, you are asked to output a new array B where B[j] is equal to the multiplication of all the elements of A except A[j], That is, for any j {1, 2, ..., n}. B[j] = Pi_i {1, 2, .., n} and i notequalto j A[i] Solve this problem in linear time. Solve this problem in linear time and without using the division operator.

Solution

Algorithm ArrayOfProducts(A[1..n])
C[1] = 1
for i <- 2 to n  
C[i] <- C[i-1] * A[i-1]
D[n] <- 1
for i <- n-1 down to 1
D[i] <- D[i+1] * A[i+1]
for i <- 1 to n
B[i] <- C[i] * D[i]

return B.

The above algorithm is using a total of 3 individual loops which runs for n times atmost. So, the algorithm is linear.

And this is not using any division operation.