@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.
