Interview Q: given an array of numbers, return array of products of all other numbers (no division)
There is 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 multiplication 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) and constant space.
Input : [1, 2, 3, 4, 5]
Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
= [120, 60, 40, 30, 24]
Solve it without division operator and in O(n) and constant space.
Input : [1, 2, 3, 4, 5]
Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
= [120, 60, 40, 30, 24]
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.
ReplyDeleteThen P[n] = B[n-1] * C[n+1]