From: "krusty.ar@..." <krusty.ar@...>
Date: 2008-06-20T23:33:38+09:00
Subject: Re: little problem (google hiring puzzle)

On Jun 15, 1:59 pm, ex <exeQ...@gmail.com> 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).
> #===============================================================================

Hi, I'm new to this list, here is an implementation that uses just
array index (and pop). With ugly intrumentation.

def resolve(i)
  front, back, o = [1], [1], []

  0.upto i.length - 1 do |n|
    front << i[n] * front[n]
    back << i[i.length - 1 - n] * back[n]
    @cost[@r]+=1
  end
  front.pop
  back.pop

  0.upto front.length - 1 do |n|
    o[n] = front[n] * back[ back.length - 1 - n]
    @cost[@r]+=1
  end
  p o
end

@cost = []
1.upto 10 do |@r|
  @cost[@r] = 1
  resolve([4, 3, 2, 1, 2]*@r)
end

p @cost


Lucas.