*Turing :P On Mon, Oct 17, 2011 at 3:51 PM, Ankur Garg <ankurga...@gmail.com> wrote:
> @Shashank ..+1 ..I wud say he must be given a tuning award :D :D for > solving such eternal conundrum ;) > > > > On Mon, Oct 17, 2011 at 2:37 PM, WgpShashank > <shashank7andr...@gmail.com>wrote: > >> @wladimir , its PPT (Pythagoras triplets ) but its number theory based >> approach http://en.wikipedia.org/wiki/Pythagorean_triple might not be >> good idea >> >> Here is approach : >> * >> * >> *Euclid's >> formula*[1]<http://en.wikipedia.org/wiki/Pythagorean_triple#cite_note-0> is >> a fundamental formula for generating Pythagorean triples given an arbitrary >> pair of positive integers *m* and *n* with *m* > *n*. The formula states >> that the integers p=m^2-n^2 , q=2mn r=m^2+n^2 , we have to sort the array >> in non-increasing order , then for each m>n we have to generate the all >> such p,q,r in worst case it will also requires O(N^2) such p,q,r for each >> M>N isn't it ? then its not less then O(n^2) ?? >> Even with this approach,The triple generated by Euclid's formula is >> primitive if and only if *m* and *n* are coprime and *m*-*n* is odd. If >> both *m* and *n* are odd, then *a*, *b*, and *c* will be even, and so the >> triple will not be primitive; however, dividing *a*, *b*, and *c* by 2 >> will yield a primitive triple if *m* and *n* are coprime. >> >> @all other , its similar to 3 sun , can't be done in less then O(N^2) if >> number are not in range , When the integers are in the range [-*u* ... *u >> *], 3SUM can be solved in time O(n + *u* lg *u*) by representing *S* as a >> bit vector and performing a discrete convolution using FFT. >> >> i wondered if any other algo/code/link you have which works in less then >> O(N^2) , Better if One Explain The Approach or Algorithm , You Might able to >> fill Patent :D >> >> Thanks >> Shashank >> CSE, BIT Mesra >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To view this discussion on the web visit >> https://groups.google.com/d/msg/algogeeks/-/JQWWHDKMCiAJ. >> >> 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.
