Friday, June 17, 2011

Calculate the multiplication of A[1], A[2]...A[N] but without A[i]

Problem: An array of numbers, A[1], A[2]...A[N], provide a O(N) algorithm to calculate C[i] = A[1]*A[2]...A[N]/A[i]. Division is not allowed and no extra memory space allowed.

Solution: An O(N) time and O(N) space algorithm may not be hard. It needs some thoughts to get an algorithm which doesn't require extra memory space. Here is a brilliant way from ihas1337code:

int C[N];
int left, right;
left = right = 1;

for(int i=0; i<N; i++)
{
   C[i] *= left;
   C[N-i-1] *= right;
   left *= A[i];
   right *= A[N-i-1];
}

No comments:

Post a Comment