### No division operator and O(n)

Some site said that this is a google interview question:

There is an array A[N] of N integers. You have to compose an array B[N] such that B[i] will be equal to the product of all the elements of A[] except A[i].

B[i] = (product from j = 1 to N, j not equal to i) A[i]

Example:

Input:[4, 3, 2, 1, 2]

Output:[12, 16, 24, 48, 24]

Solve it without division operator and in O(n).

Update (11/12/09) : Solution provided by Subhasis (EE, IITB) in comments!!

Update (01/01/10) : Solution for another case provided by Shantanu Gangal, BCG (CSE, IITB alumnus) in comments!!

There is an array A[N] of N integers. You have to compose an array B[N] such that B[i] will be equal to the product of all the elements of A[] except A[i].

B[i] = (product from j = 1 to N, j not equal to i) A[i]

Example:

Input:[4, 3, 2, 1, 2]

Output:[12, 16, 24, 48, 24]

Solve it without division operator and in O(n).

Update (11/12/09) : Solution provided by Subhasis (EE, IITB) in comments!!

Update (01/01/10) : Solution for another case provided by Shantanu Gangal, BCG (CSE, IITB alumnus) in comments!!

scan the list starting from 1 to get the partial products of the first n-1 terms in another array B[n]. Then scan from the end to get the partial sums of the n-1 last terms in another array C[n]. Then the answer = B[n]*C[n]

ReplyDeleteNice solution :)

ReplyDeletecould you elaborate on the solution a little bit? what exactly is stored in B[i] and C[i]?

ReplyDeleteTo make things simpler.. Lets say I make two arrays L[i] and R[i]

ReplyDeletewhere L[i] = Product of all elements left to i in A

So, A = [4,3,2,1,2]

Then, L = [1,4,12,24,24]

Similarly, R[i] is product of all elements to the right of i in A

R = [12,4,2,2,1]

Note that L and R can be calculated in O(n)

So, B[i] = L[i]*R[i] can be calculated in O(n)

B = [12, 16, 24, 48, 24]

Hope that helps!

Can we be cheeky & use the log / antilog operators :P ?

ReplyDeleteIf yes,

C[i] = log(A[i]) & E = sum(C[i])

B[i] = antilog(E - C[i])

If they disallow the cheek,

ReplyDeleteThen;

C[i] = {j=1 to i-1}Product(A[j])

D[i] = {j=i+1 to n}Product(A[j])

and B[i] = C[i]*D[i]

Since,

C[j] = C[j-1]*A[j-1] &

D[j] = D[j+1]*A[j+1]; all computations are O(n)

@Shantanu..

ReplyDeleteInteresting solution using log and anti-log operations :P Thanx.

In both cases (cheek allowed or not), correct solution. Thanx.

@Pratik

ReplyDeleteHow is L[i] O(n)?

For each element it is looping through the list to the right, so as such there are 2 loops, i.e. O(n^2)

Actually a simpler solution instead of doing separate L[i] and R[i] would be to start from 0 to n-1 and skip i, but it would still be O(n^2).

:(

@Eco-nemesis,

ReplyDeleteFor L(i) i from 1 to n , we do not need to loop through the n entries of A.

L(i) = A(1)..A(i) = L(i-1)*A(i)

and so L(i) for all n values can be calculated in O(n)

Ah, now I got it ... I had missed the part where you use the previous value of i-1.

ReplyDeleteCool.