Home » Technical Interview Questions » Array Interview Questions » Find Pythagorean Triplets from Array

Find Pythagorean Triplets from Array


Reading Time - 2 mins

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]

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.

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;
}
6
3 4 6 5 7 8
3  4  5

Complexity Analysis to Find Pythagorean Triplets from Array

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.

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;
}
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
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions