Posted on by Kalkicode
Code Array

# Find pythagorean triplet in array

Finding Pythagorean triplets in an array. A Pythagorean triplet consists of three positive integers `a`, `b`, and `c` such that `a^2 + b^2 = c^2`. The task is to identify and display all Pythagorean triplets from a given array of integers.

For example, given an array `[6, 29, 4, 15, 8, 20, 11, 17, 10, 21]`, we need to find and display all Pythagorean triplets.

## Problem Statement

The problem requires identifying and displaying all Pythagorean triplets from a given array of integers.

## Explanation with Example

Let's consider the example provided: array `[6, 29, 4, 15, 8, 20, 11, 17, 10, 21]`.

We need to find and display all Pythagorean triplets:

• `6² + 8² = 10²`
• `8² + 15² = 17²`
• `20² + 21² = 29²`

## Idea to Solve the Problem

To solve this problem, we can follow these steps:

1. Create an auxiliary array and copy the elements from the original array to it.
2. Square each element in the auxiliary array.
3. Sort the auxiliary array in ascending order.
4. Iterate through the auxiliary array using two pointers technique to find Pythagorean triplets.

## Pseudocode

``````Function printArray(arr, size):
Loop i from 0 to size - 1:
Print arr[i] and a space

Function findPythagoreanTriplet(arr, n):
If n is less than or equal to 2:
Return

status = false
a, b, c, left, right = 0
left = n - 2
right = n - 1
Create an auxiliary array temp of size n
Copy array elements from arr to temp

Loop i from 0 to n - 1:
temp[i] = temp[i] * temp[i]

Sort temp in ascending order

Loop i from 0 to n - 1:
a = temp[i]
Loop while left > i:
c = temp[right]
b = temp[left]
If c - b equals a:
Display the Pythagorean triplet
Increment right and left
Set status to true
Else if c - b > a:
Decrement right
Else:
Decrement left
Reset left and right values

If status is false:
Display "None"

Main:
Define array elements
n = size of array
Call findPythagoreanTriplet(arr, n)``````

## Algorithm Explanation

1. The `findPythagoreanTriplet` function calculates the squares of each element in the array and stores them in the auxiliary array `temp`.
2. It sorts the auxiliary array `temp` in ascending order.
3. Using two pointers technique (`left` and `right`), the function iterates through the array to find Pythagorean triplets.
4. When a Pythagorean triplet is found, it is displayed along with its square roots.
5. If no valid Pythagorean triplets are found, the function displays "None".

## Code Solution

``````import java.util.Arrays;
/*
Java program for
Find pythagorean triplet in array
*/
public class PythagoreanTriplet
{
// Display array elements
public void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
}
public void findPythagoreanTriplet(int[] arr, int n)
{
if (n <= 2)
{
return;
}
// result indicator
boolean status = false;
// Auxiliary variables
int a = 0;
int b = 0;
int c = 0;
int left = n - 2;
int right = n - 1;
// Auxiliary array
int[] temp = new int[n];
// Copy array elements
for (int i = 0; i < n; ++i)
{
temp[i] = arr[i];
}
// Sort array elements
Arrays.sort(temp);
// Calculate square of each element
for (int i = 0; i < n; ++i)
{
temp[i] = temp[i] * temp[i];
}
for (int i = 0; i < n; ++i)
{
a = temp[i];
while (left > i)
{
c = temp[right];
b = temp[left];
if ((c - b) == a)
{
// Display pythagorean triplet pair
System.out.print("\n" +
((int) Math.sqrt(a)) + "² + " +
((int) Math.sqrt(b)) + "² = " +
((int) Math.sqrt(c)) + "²");
right--;
left++;
status = true;
}
else if ((c - b) > a)
{
right--;
}
else
{
left--;
}
}
// Reset the left and right value
left = n - 2;
right = n - 1;
}
if (status == false)
{
System.out.print("\n None \n");
}
}
public static void main(String[] args)
{
int[] arr = {
6 , 29 , 4 , 15 , 8 , 20 , 11 , 17 , 10 , 21
};
int n = arr.length;
/*
6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²
*/
}
}``````

#### Output

``````6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²``````
``````// Include header file
#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;
/*
C++ program for
Find pythagorean triplet in array
*/
class PythagoreanTriplet
{
public:
// Display array elements
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
}
void findPythagoreanTriplet(int arr[], int n)
{
if (n <= 2)
{
return;
}
// result indicator
bool status = false;
// Auxiliary variables
int a = 0;
int b = 0;
int c = 0;
int left = n - 2;
int right = n - 1;
// Auxiliary array
int temp[n];
// Copy array elements
for (int i = 0; i < n; ++i)
{
temp[i] = arr[i];
}
// Sort array elements
sort(temp, temp + n);
// Calculate square of each element
for (int i = 0; i < n; ++i)
{
temp[i] = temp[i] *temp[i];
}
for (int i = 0; i < n; ++i)
{
a = temp[i];
while (left > i)
{
c = temp[right];
b = temp[left];
if ((c - b) == a)
{
// Display pythagorean triplet pair
cout << "\n" << ((int) sqrt(a))
<< "² + " << ((int) sqrt(b))
<< "² = " << ((int) sqrt(c)) << "²";
right--;
left++;
status = true;
}
else if ((c - b) > a)
{
right--;
}
else
{
left--;
}
}
// Reset the left and right value
left = n - 2;
right = n - 1;
}
if (status == false)
{
cout << "\n None \n";
}
}
};
int main()
{
int arr[] = {
6 , 29 , 4 , 15 , 8 , 20 , 11 , 17 , 10 , 21
};
int n = sizeof(arr) / sizeof(arr[0]);
/*
6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²
*/
return 0;
}``````

#### Output

``````6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²``````
``````// Include namespace system
using System;
/*
Csharp program for
Find pythagorean triplet in array
*/
public class PythagoreanTriplet
{
// Display array elements
public void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
}
public void findPythagoreanTriplet(int[] arr, int n)
{
if (n <= 2)
{
return;
}
// result indicator
Boolean status = false;
// Auxiliary variables
int a = 0;
int b = 0;
int c = 0;
int left = n - 2;
int right = n - 1;
// Auxiliary array
int[] temp = new int[n];
// Copy array elements
for (int i = 0; i < n; ++i)
{
temp[i] = arr[i];
}
// Sort array elements
Array.Sort(temp);
// Calculate square of each element
for (int i = 0; i < n; ++i)
{
temp[i] = temp[i] * temp[i];
}
for (int i = 0; i < n; ++i)
{
a = temp[i];
while (left > i)
{
c = temp[right];
b = temp[left];
if ((c - b) == a)
{
// Display pythagorean triplet pair
Console.Write("\n" + ((int) Math.Sqrt(a)) +
"² + " + ((int) Math.Sqrt(b)) + "² = " +
((int) Math.Sqrt(c)) + "²");
right--;
left++;
status = true;
}
else if ((c - b) > a)
{
right--;
}
else
{
left--;
}
}
// Reset the left and right value
left = n - 2;
right = n - 1;
}
if (status == false)
{
Console.Write("\n None \n");
}
}
public static void Main(String[] args)
{
int[] arr = {
6 , 29 , 4 , 15 , 8 , 20 , 11 , 17 , 10 , 21
};
int n = arr.Length;
/*
6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²
*/
}
}``````

#### Output

``````6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²``````
``````package main
import "sort"
import "math"
import "fmt"
/*
Go program for
Find pythagorean triplet in array
*/

// Display array elements
func printArray(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
}
func findPythagoreanTriplet(arr[] int, n int) {
if n <= 2 {
return
}
// result indicator
var status bool = false
// Auxiliary variables
var a int = 0
var b int = 0
var c int = 0
var left int = n - 2
var right int = n - 1
// Auxiliary array
var temp = make([] int, n)
// Copy array elements
for i := 0 ; i < n ; i++ {
temp[i] = arr[i]
}
// Sort array elements
sort.Ints(temp)
// Calculate square of each element
for i := 0 ; i < n ; i++ {
temp[i] = temp[i] * temp[i]
}
for i := 0 ; i < n ; i++ {
a = temp[i]
for (left > i) {
c = temp[right]
b = temp[left]
if (c - b) == a {
// Display pythagorean triplet pair
fmt.Print("\n", (int(math.Sqrt(float64(a)))), "² + ",
int(math.Sqrt(float64(b))), "² = ",
int(math.Sqrt(float64(c))), "²")
right--
left++
status = true
} else if (c - b) > a {
right--
} else {
left--
}
}
// Reset the left and right value
left = n - 2
right = n - 1
}
if status == false {
fmt.Print("\n None \n")
}
}
func main() {

var arr = [] int {6,29, 4, 15, 8 ,20, 11, 17 , 10, 21}
var n int = len(arr)
/*
6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²
*/
findPythagoreanTriplet(arr, n)
}``````

#### Output

``````6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²``````
``````<?php
/*
Php program for
Find pythagorean triplet in array
*/
class PythagoreanTriplet
{
// Display array elements
public	function printArray(\$arr, \$n)
{
for (\$i = 0; \$i < \$n; ++\$i)
{
echo(" ".\$arr[\$i]);
}
}
public	function findPythagoreanTriplet(\$arr, \$n)
{
if (\$n <= 2)
{
return;
}
// result indicator
\$status = false;
// Auxiliary variables
\$a = 0;
\$b = 0;
\$c = 0;
\$left = \$n - 2;
\$right = \$n - 1;
// Auxiliary array
\$temp = array_fill(0, \$n, 0);
// Copy array elements
for (\$i = 0; \$i < \$n; ++\$i)
{
\$temp[\$i] = \$arr[\$i];
}
// Sort array elements
sort(\$temp);
// Calculate square of each element
for (\$i = 0; \$i < \$n; ++\$i)
{
\$temp[\$i] = \$temp[\$i] * \$temp[\$i];
}
for (\$i = 0; \$i < \$n; ++\$i)
{
\$a = \$temp[\$i];
while (\$left > \$i)
{
\$c = \$temp[\$right];
\$b = \$temp[\$left];
if ((\$c - \$b) == \$a)
{
// Display pythagorean triplet pair
echo("\n".((int) sqrt(\$a)).
"² + ".((int) sqrt(\$b)).
"² = ".((int) sqrt(\$c)).
"²");
\$right--;
\$left++;
\$status = true;
}
else if ((\$c - \$b) > \$a)
{
\$right--;
}
else
{
\$left--;
}
}
// Reset the left and right value
\$left = \$n - 2;
\$right = \$n - 1;
}
if (\$status == false)
{
echo("\n None \n");
}
}
}

function main()
{
\$arr = array(6, 29, 4, 15, 8, 20, 11, 17, 10, 21);
\$n = count(\$arr);
/*
6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²
*/
}
main();``````

#### Output

``````6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²``````
``````/*
Node JS program for
Find pythagorean triplet in array
*/
class PythagoreanTriplet
{
// Display array elements
printArray(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
}
findPythagoreanTriplet(arr, n)
{
if (n <= 2)
{
return;
}
// result indicator
var status = false;
// Auxiliary variables
var a = 0;
var b = 0;
var c = 0;
var left = n - 2;
var right = n - 1;
// Auxiliary array
var temp = Array(n).fill(0);
// Copy array elements
for (var i = 0; i < n; ++i)
{
temp[i] = arr[i];
}
// Sort array elements
temp.sort(function(a, b)
{
return a - b;
});
// Calculate square of each element
for (var i = 0; i < n; ++i)
{
temp[i] = temp[i] * temp[i];
}
for (var i = 0; i < n; ++i)
{
a = temp[i];
while (left > i)
{
c = temp[right];
b = temp[left];
if ((c - b) == a)
{
// Display pythagorean triplet pair
process.stdout.write("\n" + (Math.sqrt(a)) + "² + " +
( Math.sqrt(b)) + "² = " +
( Math.sqrt(c)) + "²");
right--;
left++;
status = true;
}
else if ((c - b) > a)
{
right--;
}
else
{
left--;
}
}
// Reset the left and right value
left = n - 2;
right = n - 1;
}
if (status == false)
{
process.stdout.write("\n None \n");
}
}
}

function main()
{
var arr = [6, 29, 4, 15, 8, 20, 11, 17, 10, 21];
var n = arr.length;
/*
6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²
*/
}
main();``````

#### Output

``````6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²``````
``````import math
#    Python 3 program for
#    Find pythagorean triplet in array
class PythagoreanTriplet :
#  Display list elements
def printArray(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1

def findPythagoreanTriplet(self, arr, n) :
if (n <= 2) :
return

#  result indicator
status = False
#  Auxiliary variables
a = 0
b = 0
c = 0
left = n - 2
right = n - 1
#  Auxiliary list
temp = [0] * (n)
i = 0
#  Copy list elements
while (i < n) :
temp[i] = arr[i]
i += 1

#  Sort list elements
temp.sort()
i = 0
#  Calculate square of each element
while (i < n) :
temp[i] = temp[i] * temp[i]
i += 1

i = 0
while (i < n) :
a = temp[i]
while (left > i) :
c = temp[right]
b = temp[left]
if ((c - b) == a) :
#  Display pythagorean triplet pair
print("\n", int(math.sqrt(a)) ,"² + ",
int(math.sqrt(b)) ,"² = ",
int(math.sqrt(c)) ,"²", end = "",sep="")
right -= 1
left += 1
status = True
elif ((c - b) > a) :
right -= 1
else :
left -= 1

#  Reset the left and right value
left = n - 2
right = n - 1
i += 1

if (status == False) :
print("\n None ")

def main() :
arr = [6, 29, 4, 15, 8, 20, 11, 17, 10, 21]
n = len(arr)
#  6² + 8² = 10²
#  8² + 15² = 17²
#  20² + 21² = 29²

if __name__ == "__main__": main()``````

#### Output

``````6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²``````
``````#    Ruby program for
#    Find pythagorean triplet in array
class PythagoreanTriplet
#  Display array elements
def printArray(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end

end

def findPythagoreanTriplet(arr, n)
if (n <= 2)
return
end

#  result indicator
status = false
#  Auxiliary variables
a = 0
b = 0
c = 0
left = n - 2
right = n - 1
#  Auxiliary array
#  Sort array elements
temp = arr.sort
i = 0
#  Calculate square of each element
while (i < n)
temp[i] = temp[i] * temp[i]
i += 1
end

i = 0
while (i < n)
a = temp[i]
while (left > i)
c = temp[right]
b = temp[left]
if ((c - b) == a)
#  Display pythagorean triplet pair
print("\n", (Math.sqrt(a).to_i) ,"²+",
(Math.sqrt(b).to_i) ,"² = ", (Math.sqrt(c).to_i) ,"²")
right -= 1
left += 1
status = true
elsif ((c - b) > a)
right -= 1
else

left -= 1
end

end

#  Reset the left and right value
left = n - 2
right = n - 1
i += 1
end

if (status == false)
print("\n None \n")
end

end

end

def main()
arr = [6, 29, 4, 15, 8, 20, 11, 17, 10, 21]
n = arr.length
#  6² + 8² = 10²
#  8² + 15² = 17²
#  20² + 21² = 29²
end

main()``````

#### Output

``````6²+8² = 10²
8²+15² = 17²
20²+21² = 29²``````
``````import scala.collection.mutable._;
/*
Scala program for
Find pythagorean triplet in array
*/
class PythagoreanTriplet()
{
// Display array elements
def printArray(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
}
def findPythagoreanTriplet(arr: Array[Int], n: Int): Unit = {
if (n <= 2)
{
return;
}
// result indicator
var status: Boolean = false;
// Auxiliary variables
var a: Int = 0;
var b: Int = 0;
var c: Int = 0;
var left: Int = n - 2;
var right: Int = n - 1;
// Auxiliary array
// Sort array elements
var temp: Array[Int]  = arr.sorted;
var i = 0;
// Calculate square of each element
while (i < n)
{
temp(i) = temp(i) * temp(i);
i += 1;
}
i = 0;
while (i < n)
{
a = temp(i);
while (left > i)
{
c = temp(right);
b = temp(left);
if ((c - b) == a)
{
// Display pythagorean triplet pair
print("\n" + (scala.math.sqrt(a).toInt) + "² + " +
(scala.math.sqrt(b).toInt) + "² = " +
(scala.math.sqrt(c).toInt) + "²");
right -= 1;
left += 1;
status = true;
}
else if ((c - b) > a)
{
right -= 1;
}
else
{
left -= 1;
}
}
// Reset the left and right value
left = n - 2;
right = n - 1;
i += 1;
}
if (status == false)
{
print("\n None \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: PythagoreanTriplet = new PythagoreanTriplet();
var arr: Array[Int] = Array(6, 29, 4, 15, 8, 20, 11, 17, 10, 21);
var n: Int = arr.length;
/*
6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²
*/
}
}``````

#### Output

``````6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²``````
``````import Foundation;
/*
Swift 4 program for
Find pythagorean triplet in array
*/
class PythagoreanTriplet
{
// Display array elements
func printArray(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
}
func findPythagoreanTriplet(_ arr: [Int], _ n: Int)
{
if (n <= 2)
{
return;
}
// result indicator
var status: Bool = false;
// Auxiliary variables
var a: Int = 0;
var b: Int = 0;
var c: Int = 0;
var left: Int = n - 2;
var right: Int = n - 1;
// Auxiliary array
var temp: [Int] = Array(repeating: 0, count: n);
var i: Int = 0;
// Copy array elements
while (i < n)
{
temp[i] = arr[i];
i += 1;
}
// Sort array elements
temp = temp.sorted();
i = 0;
// Calculate square of each element
while (i < n)
{
temp[i] = temp[i] * temp[i];
i += 1;
}
i = 0;
while (i < n)
{
a = temp[i];
while (left > i)
{
c = temp[right];
b = temp[left];
if ((c - b) == a)
{
// Display pythagorean triplet pair
print((Int(Double(a).squareRoot())) ,"² + ",
(Int(Double(b).squareRoot())) ,"² = ",
(Int(Double(c).squareRoot())) ,"²");
right -= 1;
left += 1;
status = true;
}
else if ((c - b) > a)
{
right -= 1;
}
else
{
left -= 1;
}
}
// Reset the left and right value
left = n - 2;
right = n - 1;
i += 1;
}
if (status == false)
{
print("\n None ");
}
}
}
func main()
{
let arr: [Int] = [6, 29, 4, 15, 8, 20, 11, 17, 10, 21];
let n: Int = arr.count;
/*
6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²
*/
}
main();``````

#### Output

``````6 ² +  8 ² =  10 ²
8 ² +  15 ² =  17 ²
20 ² +  21 ² =  29 ²``````
``````/*
Kotlin program for
Find pythagorean triplet in array
*/
class PythagoreanTriplet
{
// Display array elements
fun printArray(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
}
fun findPythagoreanTriplet(arr: Array < Int > , n: Int): Unit
{
if (n <= 2)
{
return;
}
// result indicator
var status: Boolean = false;
// Auxiliary variables
var a: Int ;
var b: Int ;
var c: Int ;
var left: Int = n - 2;
var right: Int = n - 1;
// Auxiliary array
var temp: Array < Int > = Array(n)
{
0
};
var i: Int = 0;
// Copy array elements
while (i < n)
{
temp[i] = arr[i];
i += 1;
}
// Sort array elements
temp.sort();
i = 0;
// Calculate square of each element
while (i < n)
{
temp[i] = temp[i] * temp[i];
i += 1;
}
i = 0;
while (i < n)
{
a = temp[i];
while (left > i)
{
c = temp[right];
b = temp[left];
if ((c - b) == a)
{
// Display pythagorean triplet pair
print("\n" + (Math.sqrt(a.toDouble()).toInt()) + "² + " +
(Math.sqrt(b.toDouble()).toInt()) + "² = " +
(Math.sqrt(c.toDouble()).toInt()) + "²");
right -= 1;
left += 1;
status = true;
}
else if ((c - b) > a)
{
right -= 1;
}
else
{
left -= 1;
}
}
// Reset the left and right value
left = n - 2;
right = n - 1;
i += 1;
}
if (status == false)
{
print("\n None \n");
}
}
}
fun main(args: Array < String > ): Unit
{
val arr: Array < Int > = arrayOf(6, 29, 4, 15, 8, 20, 11, 17, 10, 21);
val n: Int = arr.count();
/*
6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²
*/
}``````

#### Output

``````6² + 8² = 10²
8² + 15² = 17²
20² + 21² = 29²``````

## Time Complexity Analysis

• The `findPythagoreanTriplet` function sorts the auxiliary array, which has a time complexity of O(n log n), where n is the number of elements in the array.
• The nested loops also contribute to the time complexity, but overall, the sorting dominates the time complexity.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post