Product of all elements without current one in an array

Let's understand the question first

Given an array [2, 3, 4], and you need to product an array [3*4, 2*4, 2*3] => [12, 8, 6]

In other words, current element is removed and multiply the rest of elements.

It is easy to use two loops to solve the problem, but the runtime is $\mathcal{O}(n^2)$

How to solve the problem with runtime $\mathcal{O}(n)$, but you allow to use space $\mathcal{O}(n)$

Here is the trick with dynamic programming.

Given an array [2, 3, 4], and you need to product an array [3*4, 2*4, 2*3] => [12, 8, 6]

In other words, current element is removed and multiply the rest of elements.

It is easy to use two loops to solve the problem, but the runtime is $\mathcal{O}(n^2)$

How to solve the problem with runtime $\mathcal{O}(n)$, but you allow to use space $\mathcal{O}(n)$

Here is the trick with dynamic programming.

/** * Multiply all integers except the current one * No Division is allowed * Runtime is O(n) * * [2, 3, 4] => [3*4, 2*4, 2*3] => [12, 8, 6] * * [_, 3, 4] => 3*4 * [2, _, 4] => 2*4 * [2, 3, _] => 2*3 * * 1. Use arr1[] and arr2[] as accumulators * 2. arr1[0] and arr2[len-1] as initial values * 3. arr1[i+1] = arr1[i]*arr[i] * 4. [i]*[i] => [i+1] */ public static int[] multiply(int[] arr){ if (arr == null){ throw new IllegalArgumentException("arr must not be null."); }else{ int len = arr.length; int[] acc1 = new int[len]; int[] acc2 = new int[len]; if(len > 1){ // accumulators acc1[], acc2[] acc1[0] = acc2[len - 1] = 1; for(int i=1; i < len; i++){ acc1[i] = arr[i - 1]*acc1[i - 1]; // inverse index acc2[len - 1 - i] = arr[len - i - (i-1)]*acc2[len - 1 - (i - 1)]; } for(int i=0; i < len; i++) acc1[i] = acc1[i]*acc2[i]; } return acc1; } }