That’s another simple algorithmic challenge.

Q. Given an array of integers A of size N > 1, produce an output array B of size N with B[i] = A[1]*A[2]…*A[i – 1]*A[i + 1]…*A[N], that is multiplies all elements in A except A[i] itself. Do it in linear time O(N) without using division.

Please think about it first before looking at my answer and I hope there is a better one than mine.

My solution (written in Java):

void mul(int[] a, int[] b) {
// Compute b[i] = a[0]a[1]...a[i]
b[0] = a[0];
for (int i = 1; i < a.length; i++) {
b[i] = b[i - 1] * a[i];
}
// Compute result, with v = a[n - 1]a[n - 2]...a[i] after loop i
int v = 1;
for (int i = a.length - 1; i > 0; i--) {
b[i] = b[i - 1] * v;
v *= a[i];
}
b[0] = v;
}

### Like this:

Like Loading...

*Related*

Your implementation gives O(N^2)

Can you point out where?? There are only two for-loop, each of them loop for N times, which yield O(N) time complexity.