## Nov 2, 2009

### 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!!

#### 10 comments:

1. 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]

2. Nice solution :)

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

4. To make things simpler.. Lets say I make two arrays L[i] and R[i]
where 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!

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

If yes,
C[i] = log(A[i]) & E = sum(C[i])
B[i] = antilog(E - C[i])

6. If they disallow the cheek,
Then;
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)

7. @Shantanu..
Interesting solution using log and anti-log operations :P Thanx.

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

8. @Pratik

How 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).

:(

9. @Eco-nemesis,

For 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)

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

Cool.

### Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...