From: Martin DeMello <martindemello@...>
Date: 2008-06-20T07:56:28+09:00
Subject: Re: little problem (google hiring puzzle)

On Thu, Jun 19, 2008 at 10:23 AM, Ragunathan Pattabiraman
<ragunathan.pattabiraman@gmail.com> wrote:
>
> But simplicity is the virtue that is missing IMHO. I thought I would
> attempt at simplicity. But as you pointed out it is not efficient at
> all. ("It's another Ruby virtue" says Ruby critic!)

There's a very simple solution (which I think someone has posted
upthread). The idea is this: you calculate the partial products from
each end of the array. Then, e.g.  product(all except x_10) =
product(x0..x9) * product(x11..x20). The code is straightforward, too
(but untested):

pre = []
post = []
prod = 1
n = ary.length - 1

0.upto(n) {|i|
  prod *= ary[i]
  pre[i] = prod
}

prod = 1
n.downto(0) {|i|
  prod *= ary[i]
  post[i] = prod
}

product_except = lambda {|i| pre[i-1] * post[i+1]}

Time complexity = O(n) to calculate pre, O(n) to calculate post and
O(1) to calculate product_except(i) for any i, O(n) to calculate them
all for a total of O(n).

martin