Author |
Topic: Multiplications of any N-1 elements (Read 908 times) |
|
cssomnath
Newbie
Posts: 20
|
 |
Multiplications of any N-1 elements
« on: Nov 20th, 2004, 3:00am » |
 Quote  Modify
|
I got the following problem from a site. It was written that the problem had been asked in Google interview.
Given N floating numbers, you are asked to compute the multiplications of any (N-1) of them, i.e.
Output(i) = input(1) * … input(i -1) * input(i + 1) * … input(N), for i=1 to N
If division is NOT allowed, how can you accomplish the above task in O(N) complexity?
Just to clarify you need to compute all Output(i) for i= 1 to N in O(N)
|
| « Last Edit: Nov 20th, 2004, 3:01am by cssomnath » |
 IP Logged |
|
|
|
cssomnath
Newbie
Posts: 20
|
|
Re: Multiplications of any N-1 elements
« Reply #1 on: Nov 20th, 2004, 3:37am » |
Quote Modify
|
A possible solution:
I don't know how to make it hidden
for(int i=2; i<MAX_LEN; i++) {
output[i] = output[i-1]* input[i-1];
}
//
//At this step Output[i] contains product of input[1] ... input[i-1]
//
//
//Now mutiply Output[i] with Temp where temp is a product of input[N] ... input[i+1]
//
int temp =input[MAX_LEN-1];
for(int i=MAX_LEN -2; i>=0; i--) {
output[i]*= temp;
temp *= input[i];
}
|
| « Last Edit: Nov 20th, 2004, 3:37am by cssomnath » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
|
Re: Multiplications of any N-1 elements
« Reply #2 on: Nov 20th, 2004, 10:53am » |
Quote Modify
|
Your solution looks right.
You can use hide tags: [ hide ] Solution [ /hide ] to hide the text (without the spaces). So it looks something like:
(Highlight to view) This text is hidden ...
|
| « Last Edit: Nov 20th, 2004, 10:54am by Aryabhatta » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Multiplications of any N-1 elements
« Reply #3 on: Nov 21st, 2004, 7:31am » |
Quote Modify
|
To keep it short, I'll use matlab notation (it can deal with whole vectors)
a = log(input);
b = sum(a);
output = exp(b-a);
that should about work 
Who needs division or multiplication if you can use logarithms, addition and subtraction.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print