+1 @ anurag's solution.....agree with O(sqrt(n)) complexity. --
Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad <http://gplus.to/amolsharma99> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/> On Thu, Mar 22, 2012 at 11:42 AM, Anurag Gupta <anurag.gupta...@gmail.com>wrote: > I think this works and the complexity is O(sqrt(n)) > > > #include<cmath> > #include<cstdio> > #include<iostream> > #include<cstring> > #include<cstdlib> > using namespace std; > # define INFY 1000000007 > int main() > { > int n, i, j; > int val, minDiv, minDis; > while(1) > { > cin >> n; > minDis = INFY; > for (i = n; i <= n+2; i++) > { > for (j = 1; j*j <= i; j++) > { > if (i % j == 0 && minDis > (i/j - j) ) > { > minDis = i/j - j; > minDiv = j; > val = i; > } > } > } > cout<<val<<" "<<minDiv<<" "<<val/minDiv<<endl; > } > //system("pause"); > return 0; > } > > On Mar 22, 10:34 am, atul anand <atul.87fri...@gmail.com> wrote: > > @Rujin : mathematically point 2.2 seems straight forward but can we > achieve > > value of x and y with an algo whose complexity wud be O(sqrt(E)) ?? > > > > > > > > > > > > > > > > On Wed, Mar 21, 2012 at 2:37 PM, Rujin Cao <drizzle...@gmail.com> wrote: > > > One possible way is: > > > > > 1) Put the three candidate number together into an array [n, n + 1, n > + 2] > > > 2) Iterate each element *E* in that array and test whether *E* is a > prime > > > number > > > 2.1) If it is, there will be only one way to find the two > numbers > > > product to be *E*, i.e. {x = 1, y = E} OR {x = E, y = 1}, so the > result > > > is E - 1 > > > 2.2) Otherwise, we should choose x and y that are closest to the > > > sqrt of *E*, which is quite straight forward. > > > E.g. 72 = 8 * 9 and 72 = 2 * 36 (2 < 8 and 36 > 9, so > |9 > > > - 8| < |36 - 2|) > > > > > So total time complexity is O(sqrt(E)). > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algogeeks@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
