Find Pythagorean Triplets from Array  

Difficulty Level Medium
Frequently asked in Amazon LinkedIn MakeMyTrip Myntra Oracle
Array

Problem Statement  

We have given an array that contains n integers. We need to find the set of Pythagorean triples from the given array.
Note: Pythagorean triplets condition: a^2 + b^2 = c^2.

Example  

Input

6

[3, 4, 6, 5, 7, 8]

Please click Like if you loved this article?

Output

Pythagorean triplets: 3, 4, 5

Approach 1  

We use a brute force algorithm here :

Algorithm

Step 1: We use 3 loops such that we take a set of 3 different elements from the array.
a.    We run 3 for loops. Such that for every we take all the values b except itself. For every b we take all the values of a.
b.     a, b, c are elements from the array.

Step 2: we run the Pythagorean condition that is a*a + b*b = c*c, for all the sets of (a, b, c). we print them when it is true.
a.    If a^2 + b^2 = c^2, print a, b, c.

Implementation

C++ Program to Find Pythagorean Triplets from Array

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int N;
  cin>>N;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  int a,b,c;
  for(int i = 0; i < N-2; i++)//select an element
  {
    for(int j=i+1;j <N-1; j++)//select an element in front of the considered element
      {
        for(int k =i+2; k<N;k++)// this element will be one ahead of the previously selected element in the jus touter loop
        {
          a = arr[i];
          b = arr[j];
          c = arr[k];
          if(a*a + b*b == c*c) // if the chosen elements satisfy the pythagoras theorem then simply print the three values.
            cout << a <<"  "<<b<<"  "<<c<<endl;
            
        }
      }
  }  
  return 0;
}

Java Program to Find Pythagorean Triplets from Array

import static java.lang.Integer.max;
import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int a,b,c;
        for(int i=0;i<n-2;i++)//select an element
        {
            for(int j=i+1;j<n-1;j++)//select an element in front of the considered element
            {
                for(int k=i+2;k<n;k++)// this element will be one ahead of the previously selected element in the jus touter loop
                {
                  a = arr[i];
                  b = arr[j];
                  c = arr[k];
                  if(a*a + b*b == c*c) // if the chosen elements satisfy the pythagoras theorem then simply print the three values.
                    System.out.println(a +"  "+b+"  "+c);
                }
              }
          }
    }
}
6
3 4 6 5 7 8
3  4  5

Complexity Analysis to Find Pythagorean Triplets from Array

Time complexity

O(n^3) where n is the size of the array. Here we check the condition for every possible triplet.

See also
Boolean Parenthesization Problem

Space Complexity

O(1) because we use a few variables to calculate the answer.

Approach 2  

Algorithm

  1.   Sort the given array first using the function sort.
  2.  Instead of storing the numbers store the square of each element to directly check the Pythagorean theorem.
  3. Take a as the smallest side, for every a check the elements from the array which satisfy the condition (a = c – b). if they satisfy this condition they form Pythagorean triplet as they satisfy the condition a^2 + b^2 = c^2
    a.    for all elements in the array from start, store the first element as “a”.
    b.    store the last two elements as “b” and “c” respectively.
    c.    Check the condition “a = c – b”. if true print the sqrts of a, b, c as a set of Pythagorean triplets.
    d.    If “c – b” is greater than “a”, decrease the variable pointing at the larger element(c) so that we are checking for all “c” is this condition true or not. If “c – b” is less than a decrease the variable pointing at the smaller elements so that we are checking for all b is this condition true or not.
    e.    continue this loop for all a`s
    f.    If not found any, print no triplets.

Implementation

C++ Program to Find Pythagorean Triplets from Array

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N;
  cin>>N;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  int a,b,c;
  sort(arr,arr+N); //sort the array 
  for(int i=0; i < N; i++)
  arr[i] = (arr[i] * arr[i]); //store the square of each element to directly check the pythagoras theorem
  
  for(int i=0; i<N; i++)
  {
    int left = N-2 , right = N-1;
    a = arr[i]; // first side of the triangle
    
    while(left > i) 
    {
      b = arr[left];
      c = arr[right];
      
      int calculated_side = c - b; //if a*a + b*b = c*c then obviously c*c - b*b = a*a , we utilize this to check the condition
      if(calculated_side == a)
        {
          cout << sqrt(a) << "  "  << sqrt(b) << "  " << sqrt(c) << endl;
          left++; right--; 
        }
      else if (calculated_side > a) //if side is larger than expected then decrease  the variable pointing at the larger element
        right--;
      else // if side is smaller than expected then decrease the variable pointing at the smaller element
        left--;
    }
  }
  return 0;
}

Java Program to Find Pythagorean Triplets from Array

import static java.lang.Math.sqrt;
import java.util.Arrays;
import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int a,b,c;
        Arrays.sort(arr); //sort the array 
        for(int i=0;i<n;i++)
        arr[i] = (arr[i] * arr[i]); //store the square of each element to directly check the pythagoras theorem
        for(int i=0;i<n;i++)
        {
          int left = n-2 , right = n-1;
          a = arr[i]; // first side of the triangle
          while(left > i) 
          {
            b = arr[left];
            c = arr[right];
            int calculated_side = c - b; //if a*a + b*b = c*c then obviously c*c - b*b = a*a , we utilize this to check the condition
            if(calculated_side == a)
              {
                System.out.println((int)sqrt(a) + "  "  + (int)sqrt(b) + "  " + (int)sqrt(c));
                left++; right--; 
              }
            else if (calculated_side > a) //if side is larger than expected then decrease  the variable pointing at the larger element
              right--;
            else // if side is smaller than expected then decrease the variable pointing at the smaller element
              left--;
          }
        }
    }
}
25
3 8 4 10 6 5 12 13 27 117 165 19 176 169 44 113 24 145 143 51 149 52 173 181 125
3  4  5
5  12  13
6  8  10
24  143  145
44  117  125
52  165  173

Complexity Analysis to Find Pythagorean Triplets from Array

Time complexity

O(n^2) where n is the size of the array. Here we use two pointer methods for each I value. This leads us to O(N*N) time complexity.

See also
String Matching in an Array Leetcode Solution

Space Complexity

O(1) because we use a few variables to calculate the answer.

References

Please click Like if you loved this article?