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 a

^{2}= b

^{2}+ c

^{2}. 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`

from`1`

to`i`

, and decreases`k`

from`i`

to`0`

at the same time, until they meet. Increase`j`

if`a[j]+a[k] < a[i]`

, and decrease`k`

if the sum is greater than`a[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(n^{2}) operations, which will be the final estimate.

## No comments:

Post a Comment