CareerCup

int multiply(int *a, int fwdProduct, int indx) {
    int revProduct = 1;
    if (indx < N) {
       revProduct = multiply(a, fwdProduct*a[indx], indx+1);
       int cur = a[indx];
       a[indx] = fwdProduct * revProduct;
       revProduct *= cur;
    }
    return revProduct;
}

Use 2 arrays : fill ist array with cumulative product starting from the first element
fill 2nd array with cumulative product starting from the last array

for ( i = 0; i < n ;i ++)
{
   Result[i] = FirstArray[i-1] * SecondArray[i+1]; 
}

first multiply forward, so that b[i] contains the product of a[0]*a[1]*...*a[i-1]

b[0] = 1;
    for(int j = 1; j < b.size(); ++j) {
        b[j] = b[j - 1] * a[j - 1];
    }

and then multiply backwards and multiply every b[i] by the product of all a[i+1]*...*a[n]

int back_mult = a[a.size() - 1];
    for(int k = b.size() - 2; k >= 0; --k) {
        b[k] = b[k] * back_mult;
        back_mult *= a[k];
    }

product = a(0)*a(1)*.....*a(n)

b(0) = product / a(0)
b(1) = product/a(1)

import java.util.*;


public class Test {
    
    public static int foo(int[] A, int[] B, int index, int lp) {
        if (index == A.length)
            return 1;
        int rp = foo(A,B,index+1,lp*A[index]);
        B[index] = lp * rp;
        return A[index] * rp;
    }

    public static void main(String[] args) {
        int[] A = {1,2,3};
	int[] B = new int[A.length];
	foo(A,B,0,1);
	for (int i=0; i < B.length; i++) {
            System.out.print(B[i] + " ");
        }
        System.out.println();	
    }
}

For the solution that does not use division, is the solution O(n^2) or is it better than this