Multiplies all except itself

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;

2 thoughts on “Multiplies all except itself

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s