Find pythagorean triplets from array

Find the set of Pythagorean triples from the given array
Pythagorean triplets condition: a2 + b2 = c2

Example

Input array: [3,4,6,5,7,8]
Pythagorean triplets: 3, 4, 5
32 + 42 = 52

Method 1

We use a brute force algorithm here :

Algorithm

Time complexity: O(n^3)

Step 1 : We use 3 loops such that we take set of 3 different elements from the array.
a.    We run 3 for loops. Such that for every a 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.

Algorithm working

C++ Program

#include <bits/stdc++.h>
using namespace std;

int main()
{
	
	int arr[] = { 3,8,4,10,6,5,12,13,27}; // array
	int N = sizeof(arr)/sizeof(arr[0]);//size of array
	
	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;
}
Try It

Method 2

Algorithm

Time complexity: O(n^2)

Step 1 :  Sort the given array first using the function sort.
Step 2 : Instead of storing the numbers store the square of each element to directly check the Pythagorean theorem.
Step 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
a2 + b2 = c2
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 element 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.

Algorithm Working

C++ Program

#include <bits/stdc++.h>
using namespace std;

int main()
{
	
	int arr[] = { 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}; // array
	int N = sizeof(arr)/sizeof(arr[0]);//size of array
	
	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;
}
Try It


Next > < Prev
Scroll to Top