I came across this problem recently and found it interesting.
Say you got an input array and output array of equal length. The input array has random integers and you need to populate the output array by following this criteria.
The element at index i of the output array will the product of all the elements in the input array, excluding the element at position i.
ie output[k] = Product of i's { i=0..n-1, where i≠k }
Write a code/algo that will work the FASTEST.
cross posted at basicsuncovered.
17 comments:
What about this???
Complexity: O(n)
prd=1;
for(i=0;i<n;i++) {
prd*=input[i];
}
for(i=0;i<n;i++) {
output[i] = prd/input[i];
}
Any other solution??
Still faster.. :D
Could be utter junk:
int product = 1;
int size = input.length;
if (size == 1) {
output[0] = 0;
return;
}
for(int i=0; i < size/2; i++) {
product *= input[i] * input[size-i-1];
}
if (size % 2 == 1) {
product *= input[size/2];
}
for (int i=0; i < size; i++) {
output[i] = product/input[i];
}
//tada!!! :)
If you want faster, let me know... don't tell the answer
@Amudhan
Thanks. But still faster. :)
Why didn't I think about this???
for output also:
for (int i=0; i < size/2; i++) {
output[i] = product/input[i];
output[size-i-1] = product/input[size-i-1];
}
if (size % 2 == 1) {
output[size/2] = product/input[size/2];
}
//tadaaaaa! :)
right???
@amudhan
What if I claim, second solution is slower than the first one! :)
But there is another *faster* solution.
Hmm... Let me break down the logic in the reverse way.
There is no way (for a poor ordinary brain like mine) to construct the output array without processing the input array (multiplying all and get the product).
There is no way, in one single loop, the product is calculated and output is also populated i.e. we anyhow need 2 loops.
If the first two points are wrong there is no need for you to read further :)
So, to make the number of iterations smaller, we can safely assume that, for any array there would be a beginning and ending element so that we don't need to process these two element.
So, instead of initializing the product to 1, we can initialize it like int product = input[0] * input[size-1];
Of course, we check whether the size of input is 1 in the beginning.
so, the code would be
int size = input.length;
if (size == 1) {
output[0] = 0;
return;
}
if (size == 2) {
output[0] = input[1];
output[1] = input[0];
return;
}
int product = input[0]*input[size-1];
for (int i = 1; i < size/2; i++) {
product *= input[i]*input[size-i-1];
}
if (size % 2 == 1) {
product *= input[size/2];
}
for (int i=0; i < size; i++) {
output[i] = product/input[i];
}
//tadaa? or pooda?
//BTW, why does this stupid Blogger does not save my indentation. I have written proper code with proper indentation, but it ignore it. How to fool blogger?
@amudhan
I totally agree with the first two assumptions. I believe entha supanum cant do without that. :)
yes yours is a O(n) solution. But it takes more computational time (ie more processor cycles). So when the order of the algorithm is less does not mean that its faster always. Why? Whats spl computation with this problem and the code written? Is what we got to answer and nail the solution.
For the *stupid* blogger part, Blogger comment window is like a html editor. Its does not work like WYSIWYG editor. So you can use tools like formatmysourcecode.blogspot.com
P.S. Only interesting thing that I'm doing for the day is this. :P
One thing I can think of optimizing from Amudhan's solution is:
Capturing the value of size / 2 into a temp variable and using that in both the phases product computation and output generation. That would ease up the additional computation (size / 2) needed for every looping.
Recursion will be of no use here as it will take more time in storing the state of the function and in making a new function call.
@varun you are slightly close.
@All
Here is an alternate solution, in fact this is the usual solution.
for(i=0 ; i<len; i++)
__for(j=0 ; j<len; j++)
____if(i!=j)
______out[j]*=in[i];
If I say the above code is faster, can someone reason out why?
I am not convinced with the above solution. :( Its O(n^2) and will blow up if n is high. Isn't it?
Division might be the culprit. Check out this article "How does a computer perform division?" -- http://www.pldesignline.com/showArticle.jhtml?articleID=205600561
perfect varun. :)
One more ref from the book hacker's delight
http://books.google.co.in/books?id=iBNKMspIlqEC&lpg=PP1&dq=Hacker's%20delight&pg=PA137#v=onepage&q=&f=false
Oh man... because of the stupid computer's inability to do division simply, we are in this much trouble...
Anyways, it was one of the best blogs I ever read Vijesh... quite intriguing and interesting...
Got to know some basics :)
Thanks everyone for the comments, Indeed the learning is mutual.
what is all this about? the first post gives an O(N) solution.
An the blogger then says that an O(N)^2 solution is faster?
Yes, I get that all the N divisions will take more time than N multiplications. But it will never take more than N^2 multiplications, some N large enough.
Ok, maybe there is an N for which the blogger solution is faster but there is a higher N for which the first solution is faster.
Post a Comment