tag:blogger.com,1999:blog-6294663875929591018.post3161455638264935265..comments2023-09-24T03:12:58.137-07:00Comments on Ramblings of a techie: Find three numbers in an array which forms a maximum product (for signed integers)BragBoyhttp://www.blogger.com/profile/01173019524783723568noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-6294663875929591018.post-47330600186837130042014-10-30T08:38:42.030-07:002014-10-30T08:38:42.030-07:00@Brgadeesh why cant we just use count sort to sort...@Brgadeesh why cant we just use count sort to sort the array and then take the last three elments from the array ,as they will give the resut and count sort takes O(n).rohitwtbshttps://www.blogger.com/profile/07197490559750521578noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-73617876344733773372013-09-18T20:50:20.778-07:002013-09-18T20:50:20.778-07:00thank you very much for your contribution. just a ...thank you very much for your contribution. just a little problem, I think there might be a memory leak. testing with valgrind, whenever you allocate on heap with 'new', program is responsible to delete that after using. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-17238302353835264682010-05-23T23:46:23.654-07:002010-05-23T23:46:23.654-07:00HI Bragadeesh ,
Thank you very much...HI Bragadeesh ,<br /> Thank you very much for your reply . You r ryt. YOur solution is clean ! with O(n) time .To be clear i did not mention that your lines of code takes time . i just said it was simple .Sreekanthhttps://www.blogger.com/profile/13396051754173467829noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-54423103601154005802010-05-22T14:18:54.460-07:002010-05-22T14:18:54.460-07:00@Sreekanth: Thanks for reading and replying. Altho...@Sreekanth: Thanks for reading and replying. Although your solution is right in all ways, the speed of it is O(nlogn). The simple reason being the Arrays.sort(x). Just because a program has more lines of code does not mean that its not fast. <br /><br />Arrays.sort(x) does a quick sort within which is going to scale or increase nlogn times for each n. Whereas the solution that I've provided does the job in O(5n) = O(n) time. You can try it yourself for a huge data set.<br /><br />Thanks,<br />BragaadeeshBragBoyhttps://www.blogger.com/profile/01173019524783723568noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-51054245691760513552010-05-22T02:04:52.837-07:002010-05-22T02:04:52.837-07:00Hi Brgadeesh i can we can use this algo its simple...Hi Brgadeesh i can we can use this algo its simple <br />static int getMaxProduct(int x[]){<br /> int answer = 0;<br /> Arrays.sort(x);<br /> if(x[x.length-1]>0){<br /> answer = (x[x.length-1]*x[x.length-2]*x[x.length-3] > x[x.length-1]*x[0]*x[1])?x[x.length-1]*x[x.length-2]*x[x.length-3]:x[x.length-1]*x[0]*x[1];<br /> }else{<br /> answer = x[x.length-1]*x[x.length-2]*x[x.length-3];<br /> }<br /> <br /> return answer;<br /> }Sreekanthhttps://www.blogger.com/profile/13396051754173467829noreply@blogger.com