From: Srijayanth Sridhar <srijayanth@...>
Date: 2008-06-20T18:06:42+09:00
Subject: Re: little problem (google hiring puzzle)

>
> prod= lambda{|a| a.inject(1){|p,x| p*x}}

This inject still iterates over n-1 elements for n iterations. That is
still bound to n^2.

> => #<Proc:0xb7d708e0@(irb):1>
>
> a=[4,3,2,1,2]
> => [4, 3, 2, 1, 2]
>
> pa=[]
> => []
>
> s=a.size
> => 5
>
> s2=s-1
> => 4
>
> # here is the meat:
> # i just concat orig array so i don't need to rotate
> # then get subarrays in groups of s2 (a.size-1)
>
> a2=a+a
> => [4, 3, 2, 1, 2, 4, 3, 2, 1, 2]
>
> 1.upto(s) do |i|
>  pa << prod.call(a2[i,s2])
> end
> => 1

J