Wednesday, September 16, 2009

Find a fast solution

I came across this problem recently and found it interesting.

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.

3 comments:

  1. output[k] = factorial(n-1) for k=0
    else 0

    or I am missing something.

    ReplyDelete
  2. @Sambit
    you can get the full discussion from my other blog. http://hsejiv.blogspot.com/2009/09/find-fast-solution.html

    ReplyDelete
  3. 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