I thinking in this property but i dont know how to use :(
Euclid, in his book Elements, demonstrated that there is a infinnity of suits early Pythagoreans. Moreover, he found a formula that generates all primitive Pythagorean suits. Given two natural numbers m> n, the suit (a, b, c), where: a = m ^ 2 - n ^ 2, b = 2mn, c = m ^ 2 + n ^ 2, Wladimir Araujo Tavares *Federal University of CearĂ¡ <http://lia.ufc.br/%7Ewladimir/> Homepage <http://lia.ufc.br/%7Ewladimir/> | Maratona<https://sites.google.com/site/quixadamaratona/>| * On Thu, Oct 13, 2011 at 1:59 PM, ravindra patel <ravindra.it...@gmail.com>wrote: > Hi, > Another question I faced in Amazon F2F. > > Given an unsorted array of integers, find all triplets that satisfy x^2 + > y^2 = z^2. > > For example if given array is - 1, 3, 7, 5, 4, 12, 13 > The answer should be - > 5, 12, 13 and > 3, 4, 5 > > I suggested below algo with complexity O(n^2) - > > - Sort the array in descending order. - O(nlogn) > - square each element. - O(n) > > Now it reduces to the problem of finding all triplets(a,b,c) in a > sorted array such that a = b+c. > > The interviewer was insisting on a solution better than O(n^2) which I dont > think is feasible, but I couldn't prove that. Anyone has any idea. > > > > Thanks, > - Ravindra > > -- > 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.