tag:blogger.com,1999:blog-16805286.post7073028229166973150..comments2019-12-09T16:11:51.933+05:30Comments on ScribblinG: Find a fast solutionVijeshhttp://www.blogger.com/profile/18155433751670204131noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-16805286.post-14706105111292822202010-02-01T16:42:05.146+05:302010-02-01T16:42:05.146+05:30what is all this about? the first post gives an O(...what is all this about? the first post gives an O(N) solution. <br />An the blogger then says that an O(N)^2 solution is faster?<br /><br />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.<br /><br />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.AlfChttps://www.blogger.com/profile/09583505786753076063noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-64119770407314339792009-10-03T01:57:27.307+05:302009-10-03T01:57:27.307+05:30Thanks everyone for the comments, Indeed the learn...Thanks everyone for the comments, Indeed the learning is mutual.Vijeshhttps://www.blogger.com/profile/18155433751670204131noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-53935805085551520782009-09-25T14:46:27.859+05:302009-09-25T14:46:27.859+05:30Oh man... because of the stupid computer's ina...Oh man... because of the stupid computer's inability to do division simply, we are in this much trouble...<br /><br />Anyways, it was one of the best blogs I ever read Vijesh... quite intriguing and interesting...<br /><br />Got to know some basics :)Amudhanhttps://www.blogger.com/profile/06517557838074500370noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-22259293622551763602009-09-25T12:52:41.274+05:302009-09-25T12:52:41.274+05:30perfect varun. :)
One more ref from the book hack...perfect varun. :)<br /><br />One more ref from the book hacker's delight <br /><br />http://books.google.co.in/books?id=iBNKMspIlqEC&lpg=PP1&dq=Hacker's%20delight&pg=PA137#v=onepage&q=&f=falseVijeshhttps://www.blogger.com/profile/18155433751670204131noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-26985298955088010932009-09-25T12:47:27.424+05:302009-09-25T12:47:27.424+05:30Division might be the culprit. Check out this arti...Division might be the culprit. Check out this article "How does a computer perform division?" -- http://www.pldesignline.com/showArticle.jhtml?articleID=205600561Varunkumar Nagarajanhttps://www.blogger.com/profile/17382088053239819474noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-75091164534142883832009-09-25T12:27:27.271+05:302009-09-25T12:27:27.271+05:30I am not convinced with the above solution. :( Its...I am not convinced with the above solution. :( Its O(n^2) and will blow up if n is high. Isn't it?Varunkumar Nagarajanhttps://www.blogger.com/profile/17382088053239819474noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-50117806680834510992009-09-25T12:10:52.787+05:302009-09-25T12:10:52.787+05:30@varun you are slightly close.
@All
Here is an al...@varun you are slightly close.<br /><br />@All<br />Here is an alternate solution, in fact this is the usual solution.<br /><br />for(i=0 ; i<len; i++)<br />__for(j=0 ; j<len; j++)<br />____if(i!=j)<br />______out[j]*=in[i];<br /><br />If I say the above code is faster, can someone reason out why?Vijeshhttps://www.blogger.com/profile/18155433751670204131noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-44562921439870044142009-09-25T02:08:38.606+05:302009-09-25T02:08:38.606+05:30Recursion will be of no use here as it will take m...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.Varunkumar Nagarajanhttps://www.blogger.com/profile/17382088053239819474noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-32266806310446789312009-09-25T02:06:08.841+05:302009-09-25T02:06:08.841+05:30One thing I can think of optimizing from Amudhan&...One thing I can think of optimizing from Amudhan's solution is:<br /><br />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.Varunkumar Nagarajanhttps://www.blogger.com/profile/17382088053239819474noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-74528524475218048982009-09-24T16:12:30.504+05:302009-09-24T16:12:30.504+05:30@amudhan
I totally agree with the first two assum...@amudhan<br /><br />I totally agree with the first two assumptions. I believe entha supanum cant do without that. :)<br /><br />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.<br /><br />For the *stupid* blogger part, Blogger comment window is like a html editor. Its does not work like <a href="http://en.wikipedia.org/wiki/WYSIWYG" rel="nofollow"> WYSIWYG</a> editor. So you can use tools like <a href="http://formatmysourcecode.blogspot.com/" rel="nofollow">formatmysourcecode.blogspot.com</a><br /><br />P.S. Only interesting thing that I'm doing for the day is this. :PVijeshhttps://www.blogger.com/profile/18155433751670204131noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-2202573900854641422009-09-24T15:28:53.305+05:302009-09-24T15:28:53.305+05:30Hmm... Let me break down the logic in the reverse ...Hmm... Let me break down the logic in the reverse way.<br /><br />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).<br /><br />There is no way, in one single loop, the product is calculated and output is also populated i.e. we anyhow need 2 loops.<br /><br />If the first two points are wrong there is no need for you to read further :)<br /><br />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.<br /><br />So, instead of initializing the product to 1, we can initialize it like int product = input[0] * input[size-1];<br /><br />Of course, we check whether the size of input is 1 in the beginning.<br /><br />so, the code would be<br /><br />int size = input.length;<br />if (size == 1) {<br /> output[0] = 0;<br /> return;<br />}<br />if (size == 2) {<br /> output[0] = input[1];<br /> output[1] = input[0];<br /> return;<br />}<br />int product = input[0]*input[size-1];<br />for (int i = 1; i < size/2; i++) {<br /> product *= input[i]*input[size-i-1];<br />}<br />if (size % 2 == 1) {<br /> product *= input[size/2];<br />}<br />for (int i=0; i < size; i++) {<br /> output[i] = product/input[i];<br />}<br /><br /><br />//tadaa? or pooda?<br /><br />//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?Amudhanhttps://www.blogger.com/profile/06517557838074500370noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-23587565380663421222009-09-24T14:59:49.671+05:302009-09-24T14:59:49.671+05:30@amudhan
What if I claim, second solution is slow...@amudhan<br /><br />What if I claim, second solution is slower than the first one! :)<br /><br />But there is another *faster* solution.Vijeshhttps://www.blogger.com/profile/18155433751670204131noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-32423201290483386632009-09-24T13:12:50.262+05:302009-09-24T13:12:50.262+05:30Why didn't I think about this???
for output a...Why didn't I think about this???<br /><br />for output also:<br /><br />for (int i=0; i < size/2; i++) {<br />output[i] = product/input[i];<br />output[size-i-1] = product/input[size-i-1];<br />}<br />if (size % 2 == 1) {<br />output[size/2] = product/input[size/2];<br />}<br /><br />//tadaaaaa! :)<br /><br />right???Amudhanhttps://www.blogger.com/profile/06517557838074500370noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-58891721150995588612009-09-24T13:00:31.590+05:302009-09-24T13:00:31.590+05:30@Amudhan
Thanks. But still faster. :)@Amudhan<br /><br />Thanks. But still faster. :)Vijeshhttps://www.blogger.com/profile/18155433751670204131noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-53862230403250991662009-09-24T12:35:39.021+05:302009-09-24T12:35:39.021+05:30Could be utter junk:
int product = 1;
int size = ...Could be utter junk:<br /><br />int product = 1;<br />int size = input.length;<br />if (size == 1) {<br /> output[0] = 0;<br /> return;<br />}<br />for(int i=0; i < size/2; i++) {<br /> product *= input[i] * input[size-i-1];<br />}<br />if (size % 2 == 1) {<br /> product *= input[size/2];<br />}<br />for (int i=0; i < size; i++) {<br /> output[i] = product/input[i];<br />}<br /><br />//tada!!! :)<br /><br />If you want faster, let me know... don't tell the answerAmudhanhttps://www.blogger.com/profile/06517557838074500370noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-16919550234545255092009-09-23T11:06:34.806+05:302009-09-23T11:06:34.806+05:30Still faster.. :DStill faster.. :DVijeshhttps://www.blogger.com/profile/18155433751670204131noreply@blogger.comtag:blogger.com,1999:blog-16805286.post-64447940761752912262009-09-23T11:04:58.618+05:302009-09-23T11:04:58.618+05:30What about this???
Complexity: O(n)
prd=1;
...What about this??? <br /><br />Complexity: O(n)<i><br /> prd=1;<br /><br /> for(i=0;i<n;i++) {<br /> prd*=input[i];<br /> }<br /><br /> for(i=0;i<n;i++) {<br /> output[i] = prd/input[i];<br /> }<br /><br /></i><br /><br />Any other solution??Arun Raghavendarhttps://www.blogger.com/profile/17718723517738818726noreply@blogger.com