wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Products of other elements
        
(Message started by: william wu on Jun 20^th, 2011, 7:18pm)

Title: Products of other elements
Post by william wu on Jun 20^th, 2011, 7:18pm

Problem: You are given an array of numbers X = { x1, x2, x3, ..., xN }.

Without using division or logarithms, design an algorithm that produces the array of products

{ x2*x3*...*xN , x1*x3*...*xN, x1*x2*x4*....*xN, ... }

In other words, the ith product is the product of all numbers except the ith.

[06-21-2010: edited to clarify that logs aren't allowed -- thanks towr]

Title: Re: Products of other elements
Post by towr on Jun 20^th, 2011, 10:21pm

[hide]Can we use logs, subtraction and exponents?[/hide] :P

Title: Re: Products of other elements
Post by Grimbal on Jun 21^st, 2011, 5:57am

[hide]
Multiply the arrays
[ 1, x₁, x₁*x₂, ..., x₁*...*x_N-1 ]
and
[ x₂*...*x_N, x₃*...*x_N, ..., x_N, 1]
both of which are easy to compute in O(N).
[/hide]

Title: Re: Products of other elements
Post by william wu on Jun 21^st, 2011, 7:49am

Grimbal: Yup that was the answer I had in mind :)

Title: Re: Products of other elements
Post by JohanC on Jun 22^nd, 2011, 3:22am

Do I understand it correctly that if you reuse the input to store the output, you need one extra array for temporary results?
And that only if you resort to O(n²) calculations you can get rid of that need for extra space?

Title: Re: Products of other elements
Post by Grimbal on Jun 22^nd, 2011, 8:38am

Actually, you don't need to destroy the input nor to use an intermediate array.

x[] = input
y[] = new double[x.length];
[hide]double prod = 1;
for( i=0 ; i<x.length ; i++ ){
y[i] = prod;
prod *= x[i];
}
prod = 1;
for( i=x.length ; i-->0 ; ){
y[i] *= prod;
prod *= x[i];
}[/hide]
y[] = tadaaaa!

PS: But you are right, I wouldn't know how to do it all in one array, with no division.

Title: Re: Products of other elements
Post by william wu on Jul 23^rd, 2011, 10:41pm

It can also be done in constant space, but I do not know what the optimal runtime is in that case. My solution for the constant space case also runs in O(n^2).

Title: Re: Products of other elements
Post by agent_purge on Jul 26^th, 2011, 3:07am

Divide and conquer recursive algo using log(n) space and n*log(n) time

[hideb]
product(start, end)
{
if(start == end)
{
p = x[start];
x[start] = 1;
return p;
}

mid = (start+end)/2;
p1 = product(start, mid);
p2 = product(mid+1, end);

for(i=1; i<=mid; i++)
{
x[i] *= p2;
}

for(i=mid+1; i<=end; i++)
{
x[i] *= p1;
}

return p1*p2;
}
[/hideb]

Title: Re: Products of other elements
Post by william wu on Nov 8^th, 2011, 1:38pm

Here's my solution for constant space and quadratic time. It uses two additional registers t1 and t2.

[hide]
#include <stdio.h>
main(void) {
int a[] = {3,5,1,2,7}; // input array
int n = sizeof(a)/sizeof(int);
int t1=1, t2=1; // temp variables
int j,k; // iterators
for (k=0;k<n-1;k++) {
t2 = a[k];
a[k] = a[k+1];
for (j=k+2;j<=n-1;j++) a[k] = a[k]*a[j];
a[k] = a[k]*t1;
t1 = t1*t2;
}
a[n-1] = t1;
for (k=0;k<n;k++) printf("%d ",a[k]); // print output
// output: 70 42 210 105 30
}
[/hide]