How to find pythagorean triplets in an array faster ??
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}.generate an algorithm for doing so.
if (a, b, c) is a Pythagorean triple, then so is (ka, kb, kc) for any positive integer.
ReplyDeleteso simply find one value for a, b, and c and then you can calculate as many new ones as you want.
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".
ReplyDelete