Author |
Topic: Products of other elements (Read 1309 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Products of other elements
« on: Jun 20th, 2011, 7:18pm » |
 Quote  Modify
|
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]
|
| « Last Edit: Jun 21st, 2011, 7:48am by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Products of other elements
« Reply #1 on: Jun 20th, 2011, 10:21pm » |
Quote Modify
|
Can we use logs, subtraction and exponents? 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Products of other elements
« Reply #2 on: Jun 21st, 2011, 5:57am » |
Quote Modify
|
Multiply the arrays
[ 1, x1, x1*x2, ..., x1*...*xN-1 ]
and
[ x2*...*xN, x3*...*xN, ..., xN, 1]
both of which are easy to compute in O(N).
|
|
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Products of other elements
« Reply #4 on: Jun 22nd, 2011, 3:22am » |
Quote Modify
|
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(n2) calculations you can get rid of that need for extra space?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Products of other elements
« Reply #5 on: Jun 22nd, 2011, 8:38am » |
Quote Modify
|
Actually, you don't need to destroy the input nor to use an intermediate array.
x[] = input
y[] = new double[x.length];
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];
}
y[] = tadaaaa!
PS: But you are right, I wouldn't know how to do it all in one array, with no division.
|
| « Last Edit: Jun 22nd, 2011, 8:41am by Grimbal » |
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Products of other elements
« Reply #6 on: Jul 23rd, 2011, 10:41pm » |
Quote Modify
|
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).
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
agent_purge
Newbie
Posts: 4
|
|
Re: Products of other elements
« Reply #7 on: Jul 26th, 2011, 3:07am » |
Quote Modify
|
Divide and conquer recursive algo using log(n) space and n*log(n) time
| hidden: |
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;
}
|
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Products of other elements
« Reply #8 on: Nov 8th, 2011, 1:38pm » |
Quote Modify
|
Here's my solution for constant space and quadratic time. It uses two additional registers t1 and t2.
#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
}
|
| « Last Edit: Nov 8th, 2011, 1:39pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print