Not sure this is what you want:
product=1;
for (i=0;i<=N-1;i++) product *= A[i];
for (i=0;i<=N-1;i++) OUTPUT[i] = product/A[i];
I think this is O(n).
knk
On 6/19/08, rpattabi123
<[EMAIL PROTECTED]<[EMAIL PROTECTED]>>
wrote:
>
> There was an interesting post on ruby-talk mailing list. A problem was
> presented as 'google hiring problem'. Problem is below:
> > # 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).
>
> Since it is ruby mailing list we tried to solve it the rubyish way.
>
> 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
> A member, Ray Baxter, pointed out this was not O(n) but actually O(n^2)
> saying that the eval I used is itself O(n-1).
>
> 1. I thought the eval used here is constant time. Please let me know
> your opinion.
> 2. Is there any tool given the code computes the time complexity?
> Cheers,
> Ragu
>
>
>
