Q: How to find pythagorean triplets in an array?
OR
Q: Given an array, find all such triplets
i
,j
and k
, such that a[i]2 = a[j]2+a[k]2
Pythagorean triplet is a set {a,b,c} such that a2 = b2 + c2. Example: for array
[9, 2, 3, 4, 8, 5, 6, 10]
the output of the algorithm should be {3, 4, 5}
and {6, 8, 10}
Algorithm:
Square each element. (This takes O(n) time). This will reduce the original task to "find three numbers in array, one of which is the sum of other two".
- Sort the array in ascending order. This takes O(n log n).
- Now consider each element a[i]. If a[i]=a[j]+a[k], then, since numbers are positive and array is now sorted, k<i and j<i. To find such indexes, run a loop that increases
j
from1
toi
, and decreasesk
fromi
to0
at the same time, until they meet. Increasej
ifa[j]+a[k] < a[i]
, and decreasek
if the sum is greater thana[i]
. If the sum is equal, that's one of the answers, print it, and shift both indexes. This takes O(i) operations.
- Repeat step 2 for each index
i
. This way you'll need totally O(n2) operations, which will be the final estimate.
No comments:
Post a Comment