Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search

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

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??

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