Angle Bracket <> in Java with Examples Different types of Recursions in Java Java Lambda Filter Example Java Program for Shopping Bill Pythagorean Triplet with Given Sum Using Single Loop in Java TemporalAdjusters lastInMonth() method in Java with Examples ZIP API in Java Atomic reference in Java Digit Extraction in Java DRY (Don't Repeat Yourself) Principles in Java with Examples Empty array in Java Is main method compulsory in Java? Java I/O Operation - Wrapper Class vs Primitive Class Variables Java Program to Find the Perimeter of a Rectangle Java Thread Priority Java Type Erasure Need of Concurrent Collections in Java Nested ArrayList in Java Print Odd and Even Numbers by Two Threads in Java Square pattern in Java TemporalAdjusters next() method in Java with Examples What does start() function do in multithreading in Java Convert Number to Words Problem in Java Detect And Remove Cycle in a Single Linked List in Java Evolution of Interfaces in Java How to pad a String in Java Implementing Patricia Trie in Java Java Program to Find the Most Repeated Word in a Text File java.util.UUID class in Java ReadWriteLock Interface in Java Reference Data Types in Java Sort An Array According to The Count of Set Bits in Java Alternate Vowel and Consonant string in Java Built-in Exceptions in Java with Examples Capture the Pawns Problem in Java Collections.shuffle() Method in Java with Examples JDBC MySQL Localhost 3306 Alternate Vowel and Consonant string in Java Built-in Exceptions in Java with Examples Capture the Pawns Problem in Java Collections.shuffle() Method in Java with Examples Convert Number to Words Problem in Java Detect And Remove Cycle in a Single Linked List in Java Evolution of Interfaces in Java How to pad a String in Java Implementing Patricia Trie in Java Java Program to Find the Most Repeated Word in a Text File java.util.UUID class in Java ReadWriteLock Interface in Java Reference Data Types in Java Sort An Array According to The Count of Set Bits in Java JDBC MySQL Localhost 3306 Adding a Character as Thousands Separator to Given Number in Java Circular Primes in Java Equilibrium Index Problem in Java Java String regionMatches() Method with Examples LFU Cache Problem in Java Longest Repeating and Non-Overlapping Substring in Java Prefix Suffix Search in Java Product Array Puzzle Problem in Java Russian Doll Envelopes Problem in Java Second Most Repeated Word in a Sequence in Java Special Two-Digit Numbers in a Binary Search Tree in Java Swap Corner Words and Reverse Middle Characters in Java Toggle K bits Problem in Java Upside Down Binary Tree in Java Verbal Arithmetic Puzzle Problem in Java Insert a String into another String in Java Print Shortest Path to Print a String on Screen in Java Search Insert Position in Java BST Sequences in Java Burrows - Wheeler Data Transform Algorithm in Java Convert BST to Min Heap in Java Fibonacci Sum in Java Get name of current method being executed in Java Keith number in Java Longest Even Length Substring in Java Saint-Exupery Numbers in Java Standard practice for protecting sensitive data in Java application Strobogrammatic number in Java Types of Methods in Java Programming Valid Number Problem in Java Boggle Search Problem in Java Convert Java Object to JSON String using Jackson API Generate Random String in Java Java Program to Determine the Unicode Code Point at Given Index in Strin Java 18 snippet tags Jumping Numbers in Java Junction Numbers in Java Find Four Elements that Sums to a given value in Java How to print string vertically in Java How to remove in string in Java Three-Way Partition Problem in Java Apocalyptic Number in Java Check if the given two matrices are mirror images of one another in Java Duplicate Characters Problem in Java Duplicate Parenthesis Problem in Java Sum of Minimum and Maximum Elements of all Subarrays of Size K in Java Triple Shift Operator in Java Valid Pairing of Numbers in Java Valid Sudoku problem in Java Java Cipher Class Kth Missing Positive Number in Java Largest Square Matrix Problem in Java Length of the longest substring without repeating characters in Java Minimum Cost to Make String Valid Problem in Java Ordered pair in Java Range Addition Problem in Java

Pythagorean Triplet with Given Sum Using Single Loop in Java
2024-01-17 09:03:55

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).