Table of Contents
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]
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.
Space Complexity
O(1) because we use a few variables to calculate the answer.
Approach 2
Algorithm
- Sort the given array first using the function sort.
- Instead of storing the numbers store the square of each element to directly check the Pythagorean theorem.
- 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.
Space Complexity
O(1) because we use a few variables to calculate the answer.