Friday, January 30, 2009

Multiplying the other elements of an array in linear time

You are given an array X with n elements. Can you compute in linear time a new array A with n elements, where A[i] is the product of all elements in X, but X[i] is excluded. You cannot use division, you may use additional space

1 comment:

  1. 0. Consider the right subarray A[0....i-1] and the left subarray A[i+1 ... n-1], can you accumulate partial products in linear time??

    TS and GIO they were faster than me, in solving this one.