Get an O(N) algorithm to find a product of a collection of numbers with a strange constraint

Question

This is a question when I participated a recent interview, I think it interesting. Let's say int n=10;

Input : An array int a[10];

Output: An array float b[10];

Requirement:

b[0]= a[1]*a[2]*...a[9];  //  product of all numbers in a, other than a[0]; 
b[1]= a[0]*a[2]*...a[9];  //  product of all numbers in a, other than a[1];
....
b[9]= a[0]*a[1]*...a[8];  //  product of all numbers in a, other than a[9];
....

Problem: How can we get array b populated without using division operator /? And with a O(n) algorithm?

I tried quite a few methods, but still in vain. Any ideas?

Answer 1

Firstly, calculate all left and right products:

left[i] = a[0]*a[1]*...*a[i]
right[i] = a[i]*a[i+1]*...*a[n-1]

Note that left[i] == left[i-1] * a[i], so the left array can be computed in linear time. Simlarly, the right array can be computed in linear time.

From left and right, the array b can be computed in linear time by b[i] = left[i-1] * right[i+1] with special cases for i == 0 and i == n.

Answer 2

According to Egor Skriptunoff idea, I wrote this code:It is easier to understand:

        float l[n];
        float r[n];
        left[0] = 1;
        right[n-1] = 1;
        for (int i=1; i<n; i++)
        {
            l[i] = l[i-1]*a[i-1];
        }
        for (int i=n-2; i>=0; i--)
        {
            r[i] = r[i+1]*a[i+1];
        }
        for (int i=0; i<n; i++)
        {
            b[i] = l[i]*r[i];
        }