Pythagorean Triplet with Given Sum Using Single Loop in Java

The Pythagorean triplet can be determined as a group of natural numbers where a<b<c, and a² + b² = c². Provided with a natural number N, determine a Pythagorean triplet whose sum is equal to N, or return -1.

Example 1:

Input: 12

Output: 3 4 5

Explanation: The sum of the squares of the first two numbers is equal to the square of the third number. 3² + 4² = 5².

Example 2:

Input: 24

Output: 6 8 10

Explanation: The sum of the squares of the first two numbers is equal to the square of the third number. 6² + 8² = 10².

Example 3:

Input: 10

Output: -1

Explanation: No Pythagorean triplets are available for the provided input.

Approach

• The approach will be based on calculating the values of b and c while considering the value of a; values of a will be iterated from 1 to N.

The values of both b and c can be calculated using the following equations:

Step 1:

• a² + b² = c² and a + b + c = N

Step 2:

• The value of c can be calculated based on values of both a and b.
• The value of c will be generated by substituting it in the first equation.
• c = N - b - a

Step 3:

• The value of c calculated in step-2 will be substituted in the first equation.
• a² + b² = (N - b - a)²

Step 4:

• The above-generated equation can be simplified.
• The values of b and c generated are:
• b = ( N*N - 2*N*a) (2*N - 2*a)
• c = N - b - a

Step 5:

• A loop will be utilized to iterate from the values of 1 to N, and the value of b and c will be calculated, respectively.
• The value calculated will be checked in the second equation.

Filename: PythagoreanTriplet.java

`public class PythagoreanTriplet {    // Function which calculates the Pythagorean triplet in O(n) time complexity.    static void Pythagorean(int n) {        int cnt = 0;        // Loop iterates from 1 till N-1.        for (int a = 1; a < n; a++) {            // The value of B is calculated            int b = (n * n - 2 * n * a) / (2 * n - 2 * a);            // The value of C is calculated using the formula.            int c = n - a - b;            //Checks whether the triplet is Pythagorean Triplet or not.            if (a * a + b * b == c * c && b > 0 && c > 0) {                System.out.print(a + " " + b + " " + c);                cnt = 1;                break;            }        }            //Returns -1 if there is no triplet available.        if (cnt == 0) {            System.out.print("-1");        }        return;    }    public static void main(String[] args) {        int x = 24;        Pythagorean(x);    }}`

Output

`6 8 10`

Complexity Analysis: The time complexity of the above-mentioned approach or algorithm is O(n), where n is the input number. Whereas the space complexity of the above-mentioned approach or algorithm is O(1).