|
Given an array arr[] of n integers, construct a Product Array......
Microsoft Interview Questions and Answers
(Continued from previous question...)
32. Given an array arr[] of n integers, construct a Product Array......
Question:
Given an array arr[] of n integers, construct a Product Array prod[] (of same size) such that prod[i] is equal to the product of all the elements of arr[] except arr[i]. Solve it without division operator and in O(n).
maybe an answer1:
if element stored in int e[];
go from begin to tail, h[i]=h[i-1]*e[i]
go from tail to head, t[i]=t[i+1]*e[i]
then the result is prod[i]=h[i-1]*t[i+1]
maybe an answer2:
left_partial = 1;
right_partial = 1;
for (i = 0 ; i < n; i++)
{
prod[i] = left_partial;
left_partial *= arr[i];
}
for (i = n - 1; i >= 0; i--)
{
prod[i] *= right_partial;
right_partial *= arr[i];
}
O(n) time complexity
O(1) space complexity
(Continued on next question...)
Other Interview Questions
| 