From: Dave Thomas <dave@...>
Date: 2008-06-16T02:26:54+09:00
Subject: Re: little problem (google hiring puzzle)

How about a little cheat...

vals = [4, 3, 2, 1, 2]
sum_logs = vals.map {|v| Math.log(v)}.inject {|a,b| a+b}
p vals.map {|v| Integer(Math.exp(sum_logs - Math.log(v))) }

Dave


On Jun 15, 2008, at 11:59 AM, ex wrote:

> Hi guys, I wonder if someone can find a pure ruby solution instead of
> mine (I still can get out of my *loop* mind):
>
> ################################################################################
> #	There is an array A[N] of N integers. You have to compose an array
> #	Output[N] such that Output[i] will be equal to the product of all
> #	the elements of A[] except A[i].
> #
> #    Example:
> #        INPUT:[4, 3, 2, 1, 2]
> #        OUTPUT:[12, 16, 24, 48, 24]
> #
> #    Note: Solve it without the division operator and in O(n).
> #=
> =
> =
> =
> =
> =
> =
> =
> =
> ======================================================================
>
> vals = [4, 3, 2, 1, 2]
>
> front = []
> back = []
> mf = 1
> mb = 1
> for k in 0...vals.length
> 	front.push(mf)
> 	back.unshift(mb)
> 	mf *= vals[k]
> 	mb *= vals[vals.length - 1 - k]
> end
>
> ans = []
> front.each_index{|k| ans.push(front[k]*back[k]) }
>
> p vals
> p ans
>
>
>