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.