algorithm - Given an array of numbers, return array of products of all other numbers (no division) -

i asked question in job interview, , i'd know how others solve it. i'm comfortable java, solutions in other languages welcome.

given array of numbers, nums, return array of numbers products, products[i] product of 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 in o(n) without using division.

an explanation of polygenelubricants method is: trick construct arrays (in case 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 can done in o(n) starting @ left , right edges respectively.

then multiplying 2 arrays element element gives required result

my code this:

int a[n] // 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]; // result for(int i=0;i<n;++i) {   products[i]=products_below[i]*products_above[i]; } 

if need o(1) in space can (which less clear imho)

int a[n] // input int products[n];  // products below current index p=1; for(int i=0;i<n;++i) {   products[i]=p;   p*=a[i]; }  // products above curent index p=1; for(int i=n-1;i>=0;--i) {   products[i]*=p;   p*=a[i]; }