From: pjb@... (Pascal J. Bourguignon)
Date: 2008-06-20T18:03:35+09:00
Subject: Re: little problem (google hiring puzzle)

ex <exeQtor@gmail.com> writes:

> 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
>

def google(a)
  r=Array.new(a.length,1) 
  m=1; i=0;          while (i<a.length) do r[i]*=m; m*=a[i]; i+=1  end
  m=1; i=a.length-1; while (0<=i)       do r[i]*=m; m*=a[i]; i-=1  end
  return r
end


irb(main):060:0> google([4,3,2,1,2])
[12, 16, 24, 48, 24]

-- 
__Pascal Bourguignon__