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