I am giving a general algorithm for this problem as I don't know Ruby
Input array: A[N]
Output array : O[N]
Tmp arrays : tmp_one[N], tmp_two[N]
tmp_one[0] = 1
tmp_two[N-1] = 1
for i = 1 to N-1
tmp_one[i] = A[i-1] * tmp_one[i-1]
// After this step tmp_one[i] = tmp_one[*0*] * tmp_one[1] * ... * tmp_one[*
i-1*];
for i = N-2 to 0
tmp_two[i] = A[i+1] * tmp_two[i+1]
// After this step tmp_two[i] = tmp_two[*i+1*] * tmp_two[i+2] * ... *
tmp_two[*N-1*];
for i = 0 to N-1
output[i] = tmp_one[i] * tmp_two[i];
// here i am multiplying elements (0 to i-1) and (i+1 to N) which is
equivalent to product of all
the elements of A[] except A[i]. No division operator is used here.
I am traversing the array thrice here. So, it is of order O(n)
Aravindhan
On Tue, Jul 1, 2008 at 11:55 PM, knk <[EMAIL PROTECTED]> wrote:
> 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]<ragunathan.pattabiraman%2Btwincling%40gmail.com>
> <[EMAIL PROTECTED]<ragunathan.pattabiraman%252Btwincling%40gmail.com>
> >>
> 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
> >
> >
> >
>
>
>
[Non-text portions of this message have been removed]
