Home » Interview Questions » Array Interview Questions » Find pythagorean triplets from array

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;
}

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.

READ  Circular Queue

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;
}

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions