write a program in java to input a positive integer and find all Pythagorean triplets upto that number
eg. n=15
output= (5,3,4) (10,6,8) (13,5,12) (15,9,12)
Answers
Answer:
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}.
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(n2) operations, which will be the final estimate.
Explanation:
PLEASE MARK ME AS THE BRAINLIEST!!!