Facebook /Mircosoft interview question - Analysis + several solutions in C++/Java

Given an array A, output another array B such that B[k] is the product of all elements in A but A[k]. Division is not allowed, More specifically,

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.

Full analysis:

An explanation of the 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]; }   Here is a small recursive function in C++ to do the modification in place. It requires O(n) extra space (on stack) though. Assuming the array is in a and N holds the array length, we have 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; } //Here is a small recursive function in Java static int multiply(int[] nums, int p, int n) { return (n == nums.length) ? 1 : nums[n] * (p = multiply(nums, nums[n] * (nums[n] = p), n + 1)) + 0*(nums[n] *= p); } int[] arr = {1,2,3,4,5}; multiply(arr, 1, 0); System.out.println(Arrays.toString(arr)); // prints "[120, 60, 40, 30, 24]"    Here's another method to solve it in Java. Apologies for the non-standard formatting, but the code has a lot of duplication, and this is the best I can do to make it readable. import java.util.Arrays; public class Products { static int[] products(int... nums) { final int N = nums.length; int[] prods = new int[N]; Arrays.fill(prods, 1); for (int i = 0, pi = 1 , j = N-1, pj = 1 ; (i < N) && (j >= 0) ; pi *= nums[i++] , pj *= nums[j--] ) { prods[i] *= pi ; prods[j] *= pj ; } return prods; } public static void main(String[] args) { System.out.println( Arrays.toString(products(1, 2, 3, 4, 5)) ); // prints "[120, 60, 40, 30, 24]" } }   //Source: here