From: Ray Baxter <ray@...>
Date: 2008-06-19T04:18:01+09:00
Subject: Re: little problem (google hiring puzzle)


On Jun 18, 2008, at 11:41 AM, Ragunathan Pattabiraman wrote:

> ################################################################################
>> #  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).
>> #=
>> =
>> =
>> =
>> =
>> =
>> =
>> =
>> =
>> =
>> =====================================================================
>
> Here is my attempt:
>
> input  = [4,3,2,1,2]
> output = []
>
> input.each_index do |index|
>  odd_man_out  = input[0...index] + input[index+1..-1]
>  starry_night = odd_man_out.join('*')
>  output      << eval(starry_night)
> end
>
> puts output


This is O(n^2).

Each eval is O(n-1). You do n of them.

Ray