Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

triplet
pythagorean
array
c++
python

How to find Pythagorean triplets in an array

Educative Answers Team

A Pythagorean triplet is a set {a, b, c} such that a2=b2+c2a^2 = b^2+ c^2. The user is provided with an array of integers and has to identify all the possible sets of Pythagorean triplets.

Algorithm

The naive approach here would be to run three nested for loops to try all possible triplets in an array. However, the complexity of such a solution would be O(n3)O(n^3).

Instead, we can solve the problem in O(n2)O(n^2) by sorting the array in ascending order, first.

The steps involved would be:

  • Square every element in the input array and then sort it in ascending order.
  • Since the array now contains squares, the new equation for triplet becomes a=b+ca = b + c. Fix a to be the last element of this sorted array, since a will always have the largest value of the three numbers.
  • Fix b as the first element of the sorted array and c as the element right before element a. Since numbers are positive and the array is sorted, b<ab < a and c<ac < a. To find triplets, run a loop that increases b from 11 to nn, and decreases c from nn to 11 at the same time until they meet.
    1. Increase the position of b if b+c<ab + c < a.
    2. Decrease the position of c if b+c>ab + c > a .
    3. If the sum is equal to a, then print the square root of the three numbers, increment b, and decrement c.
    4. Repeat the last step for each element a in the array.

The following slides help us to visualize this algorithm:​

1 of 11

Code

#include <algorithm> 
#include <iostream>   
#include <math.h> 
using namespace std; 

void findTriplet(int arr[], int n) 
{ 
  // Step 1
  for (int i = 0; i < n; i++) 
    arr[i] = arr[i] * arr[i]; 

  // Sort array elements 
  sort(arr, arr + n); 

  // Step 2 and Step 3 
  for (int i = n - 1; i >= 2; i--) {  // Fixing a
    int b = 0;    // Fixing b
    int c = i - 1;    // Fixing c
    while (b < c) { 
      // A triplet found 
      if (arr[b] + arr[c] == arr[i]){
        cout << "Triplet: "<< sqrt(arr[b]) <<", "<< sqrt(arr[c]) <<", "<< sqrt(arr[i])<<"\n"; 
        b++;
        c--;
      }

      // Else either move 'b' or 'c' 
      else if (arr[b] + arr[c] < arr[i]) {
        b++;
      }
      else { 
        c--; 
      }
    } 
  } 
} 
  
// Driver code
int main() 
{ 
  int arr[] = { 3, 1, 4, 6, 5 }; 
  int n = sizeof(arr) / sizeof(arr[0]); 
  findTriplet(arr, n);
  return 0; 
} 

RELATED TAGS

triplet
pythagorean
array
c++
python
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring