N2 would me minimum On 13-Oct-2011 11:08 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.
