Say you got an input array and output array of equal length. The input array has random integers and you need to populate the output array by following this criteria.
The element at index i of the output array will the product of all the elements in the input array, excluding the element at position i.
ie output[k] = Product of i's { i=0..n-1, where i≠k }
Write a code / algo that will work the FASTEST.
output[k] = factorial(n-1) for k=0
ReplyDeleteelse 0
or I am missing something.
@Sambit
ReplyDeleteyou can get the full discussion from my other blog. http://hsejiv.blogspot.com/2009/09/find-fast-solution.html
This can be done in two passes. In first pass, get the product of the complete array. In the second pass, as you populate elements in the second array, divide the total product by element at position i in first array. Its order will still be O(n)
ReplyDelete