[Facebook] Products of all elements

Question：

Given an array of numbers, nums, return an array of numbers products, where products[i] is the product of all nums[j], j != i.

Input : [1, 2, 3, 4, 5]

Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]

      = [120, 60, 40, 30, 24]

You must do this in O(N) without using division.

[Thoughts]

An explaination of polygenelubricants method is: The trick is to construct the arrays (in the case for 4 elements)

{              1,         a[0],    a[0]*a[1],    a[0]*a[1]*a[2],  }
{ a[1]*a[2]*a[3],    a[2]*a[3],         a[3],                 1,  }

Both of which can be done in O(n) by starting at the left and right edges respectively.
Then multiplying the two arrays element by element gives the required result
My code would look something like this:

int a[N] // This is the input
int products_below[N];
p=1;
for(int i=0;i<N;++i)
{
  products_below[i]=p;
  p*=a[i];
}

int products_above[N];
p=1;
for(int i=N-1;i>=0;--i)
{
  products_above[i]=p;
  p*=a[i];
}

int products[N]; // This is the result
for(int i=0;i<N;++i)
{
  products[i]=products_below[i]*products_above[i];
}

If you need to be O(1) in space too you can do this (which is less clear IMHO)

int a[N] // This is the input
int products[N];

// Get the products below the curent index
p=1;
for(int i=0;i<N;++i)
{
  products[i]=p;
  p*=a[i];
}

// Get the products above the curent index
p=1;
for(int i=N-1;i>=0;--i)
{
  products[i]*=p;
  p*=a[i];
}

转自：

http://fisherlei.blogspot.com/2013/01/facebook-products-of-all-elements.html