I want to share a nice question that I came across on the internet. It doesn’t require knowledge of any algorithm so even beginners can attempt it.

There is an array of size n, a[n]. The objective is to construct another array of size n, lets call it b[n].

The array b should be such that b[i] (0<=i<n) contains the product of all elements of the array a, except the ith element (i.e. except a[i]).

For example, if array a is

4 3 5 1 10

then the array b will be

150 200 120 600 60

Simple, right? Here’s the catch: you cannot use the division operator. n can be very large, so your solution must be efficient enough to compute the array b in a reasonable amount of time. An O(n) solution would work.

Try it!

### Like this:

Like Loading...

*Related*

Can you please post the solution to this?

This can be done using dynamic programming.

Use two extra arrays left[ ] and right[ ], both of size n

The values stored in these arrays are as follows:

left[i]= a[0] * a[1] * … * a[i-1] * a[i]

right[i]=a[i] * a[i+1] * … * a[n-2] * a[n-1]

Now array b[ ] can computed as follows:

b[i]=left[i-1] * right[i+1]

The code is: