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