Possible Duplicate:
Interview Q: given an array of numbers, return array of products of all other numbers (no division)
I came across an interview task/question that really got me thinking ... so here it goes:
You have an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplic开发者_开发问答ation of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).
I really tried to come up with a solution but I always end up with a complexity of O(n^2). Perhaps the is anyone smarter than me who can tell me an algorithm that works in O(n) or at least give me a hint...
Construct two temporary arrays - B[N] and C[N]. Form each element of B[N] as the product of the A[N] elements to its left (including itself) - working left to right, N operations. Form each element of C[N] as the product of the A[N] elements to its right (including itself) - working right to left, N operations.
Then A[n] = B[n-1] * C[n+1] - another N operations to work this out. You end up with just short of 3N operations, which is O(N). It's just short, because B[0] and C[N-1], and the first and last A, don't require multiplication. Also, C[0] = B[N-1], so I think you should need exactly 3N-5 operations.
You generate two intermediate arrays, L
, where L[i] = products of A[0]..A[i-1]
, and U
where U[i] = products of A[i+1]..A[N-1]
. These can both be generated in O(n). Your output value B[i]
will just be L[i] * U[i]
- again this is O(n).
Cheating I know but:-
for (x = 0 ; x < n ; x++) {
bigtot = bigtot * in[x];
}
for (x = 0 ; x < n ; x++) {
out[n] = bigot;
for ( y = in[x]; y > 0 ; y--) {
out[n] = out[n] - in[x]
}
}
精彩评论