@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 <[email protected]>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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
