@Coder: Sort the array into ascending order of the squares of the
values; e.g., if the data is -2, 1, 3, then the sorted result should
be 1, -2, 3 because 1*1 < (-2)*(-2) < 3*3. Then apply the following
pseudo-code:
for k = 3 to n // 1-based indexing assumed
i = 1
j = k-1
while i < j do
m = a[i]^2 + a[j]^2 - a[k]^2
if m = 0, then return a[i], a[j], and a[k] as an answer
triplet
otherwise if m < 0, then i = i+1
otherwise j = j-1
end while
end for
return failure
O(n log n) for the sort + O(n^2) for the pseudo-code = O(n^2) overall.
Dave
On Aug 6, 1:06 pm, coder dumca <[email protected]> wrote:
> given an array , find three numbers a,b and c such that a^2+b^2=c^2 in
> o(n^2)
--
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.
