Hey Ninja! Were you wondering about ways to find Pythagorean Triplets in an array? We've got you covered! This article will discuss various approaches to finding Pythagorean Triplets in an array. We will start with a brute-force approach and then gradually move on to optimized ones.

Let us begin with the basics.

Array

An array is a linear data structure used to store variables of a similar data type. All the elements of an array are referenced by a common name. You need to keep the following points about arrays in mind:

An array is a linear data structure.

Elements in an array are stored at continuous locations in the memory.

Any element of an array can be accessed using the array name and the index of that element.

The index of an array ranges from 0 to n-1, where n is the size of the array.

Look at the following image to understand it better:

Now that you know about the arrays let us see what Pythagorean Triplets are.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Pythagorean Triplets

According to Pythagoras' theorem, if we add the squares of the perpendicular and the base of any right-angled triangle, their sum will be equal to its hypotenuse. Any Triplet (i.e., a group of 3 numbers) satisfying the Pythagoras theorem is known as a Pythagorean Triplet.

In simple words, if three numbers p, q, and r satisfy the relation p^{2} + q^{2} = r^{2}, they are said to be Pythagorean Triplets.

Now let's come to our problem statement.

Problem Statement

You are given an input array that stores n integers (a1, a2,..., an), and you need to find if the array contains a Pythagorean Triplet.

A Pythagorean Triplet in an array is said to be found if it contains three integers, p, q, and r, such that p^{2} + q^{2} = r^{2}.

Before moving on to its solution, let us understand the problem first.

Explanation with Example

We will get an array of integers as input. We are supposed to write a function that returns true if there is a Pythagorean Triplet in an array. If the Pythagorean Triplet is not present in the array, then it should return false. It means that our function should return true if adding the squares of any two numbers in our array equals the square of the third one.

Now that you know the task let us look at its solutions. There are many ways to find a Pythagorean Triplet in an array. We will begin with the brute-force approach.

Brute-Force Approach

The naive approach to solving this problem is to run three nested loops. In this method, we will try to pick every possible Triplet that is present in the input array and see if it satisfies the condition of Pythagorean Triplets in an array.

Algorithm

To find Pythagorean Triplets in an array using a brute-force approach, we will follow the following algorithm:

Run three nested loops to pick three elements, p, q, and r, from the input array.

If for any value of p, q, r, the condition p^{2} = q^{2} + r^{2} is satisfied, our function will return true.

Else our function will return false.

Implementation in C++

#include <iostream>
// C++ program to find Pythagorean Triplet in an array.
using namespace std;
bool pyTriplet(int a[], int size) {
/* Example =>
A = { 5, 2, 3, 4, 1 }
^ ^ ^
i j k
Initial positions of looping variables i, j and k
*/
int p = 0, q = 0, r = 0;
for (int i = 0; i < size - 2; i++) {
for (int j = i + 1; j < size - 1; j++) {
for (int k = j + 1; k < size; k++) {
// Storing squares of each element of a Triplet
p = a[i] * a[i];
q = a[j] * a[j];
r = a[k] * a[k];
// Check the Pythagorean Triplet in an array
if (p == q + r || q == p + r || r == p + q) {
// Returns true if Pythagorean Triplet is found
return true;
}
}
}
}
// Function returns false if Pythagorean Triplet is not found
return false;
}
// Main code
int main() {
int size;
bool isPy;
cout << "Enter the size of array" << endl;
cin >> size;
cout << "Enter array elements" << endl;
int a[size];
for (int i = 0; i < size; i++) {
// Initializing array.
cin >> a[i];
}
isPy = pyTriplet(a, size);
if (isPy) {
// If pyTriplet returns true.
cout << "Pythagorean Triplet Present" << endl;
}
else {
// If pyTriplet returns false.
cout << "Pythagorean Triplet is not Present" << endl;
}
return 0;
}

Input

Enter the size of array 5
Enter array elements 5 7 12 13 14

Output

Implementation in Java

// Java program to find Pythagorean Triplet in an array
import java.io.*;
import java.util.*;
class Main {
public static boolean pyTriplet(int a[], int size) {
int p = 0, q = 0, r = 0;
for (int i = 0; i < size - 2; i++) {
for (int j = i + 1; j < size - 1; j++) {
for (int k = j + 1; k < size; k++) {
p = a[i] * a[i];
q = a[j] * a[j];
r = a[k] * a[k];
if (p == q + r || q == p + r || r == p + q) {
// If Pythagorean Triplet is found.
return true;
}
}
}
}
// If Pythagorean Triplet is not found.
return false;
}
// Main code
public static void main(String args[]) {
int size;
boolean isPy;
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of the array");
size = sc.nextInt();
int a[] = new int[size];
System.out.println("Enter the elements of the array");
for (int i = 0; i < size; i++) {
// Populating the array.
a[i] = sc.nextInt();
}
// Function call
isPy = pyTriplet(a, size);
if (isPy) {
// If function returns true.
System.out.println("Pythagorean Triplet present");
}
else {
// If function returns false.
System.out.println("Pythagorean Triplet not present");
}
}
}

Input

Enter the size of array 5
Enter array elements 5 7 12 13 14

# Python program to find pythagorean triplet in an array
def pyTriplet(a, size):
for i in range(0, size - 2):
for j in range(i + 1, size - 1):
for k in range(j + 1, size):
p = a[i] * a[i]
q = a[j] * a[j]
r = a[k] * a[k]
if p == q + r or q == p + r or r == p + q:
# Return 1(true) if Pythagorean Triplet is found.
return 1
# Return 0(false) if Pythagorean Triplet is not found.
return 0
# Main code
a = []
size = int(input("Enter size of array "))
print("enter the elements of the array")
# Populating the array
for i in range(0, size):
a_element = int(input())
a.append(a_element)
# Function call
isPy = pyTriplet(a, size)
if isPy == 1:
# If function returns 1
print("Pythagorean Triplet Present")
else:
# If function returns 0
print("Pythagorean Triplet not Present")

Input

Enter the size of array 5
Enter array elements 5 7 12 13 14

Output

Complexity

Time Complexity

O(N^{3}), where N is the number of elements in the array.

Reason: We have used three nested loops in this method. Each loop is executed until the looping variable reaches the size of the input array. The time complexity is thus O(N^{3}). Here, n is equal to the size of the input array.

Space Complexity

O(1) is the Space complexity.

Reason: The space complexity remains O(1) since we are not using any extra space.

Use of Sorting

We can also solve this problem by sorting the array first. We can reduce the time complexity of this task by sorting.

Algorithm

Square each element of the input array ( a[ ] ).

Sort the squared array in ascending order.

To find a Pythagorean Triplet (p, q, r) where p = q + r, do the following:

Fix ‘p' as the last element of your sorted array.

Initialize ‘q’ as the first element and r as the second last (p-1) element of the sorted array.

Otherwise, if a[q] + a[r] > a[p], decrement r (i.e., r --).

If you can not find a pair of q and r that satisfy the given condition for the current value of p, then move p one position back.

Repeat steps b through f until a Pythagorean Triplet is found or p reaches the second index.

Implementation in C++

#include <algorithm>
#include <iostream>
using namespace std;
bool pyTriplet(int a[], int size) {
// Square each element modifying original array.
for (int i = 0; i < size; i++) {
a[i] = a[i] * a[i];
}
// Sorting
sort(a, a + size);
for (int i = size - 1; i >= 2; i--) {
int low = 0;
int high = i - 1;
while (low < high) {
// If Pythagorean Triplet is found.
if (a[low] + a[high] == a[i]) {
return true;
}
// Otherwise move either high or low.
if (a[low] + a[high] < a[i]) {
low++;
}
else {
high--;
}
}
}
// If Pythagorean Triplet is not.
return false;
}
// Main code
int main() {
int size;
bool isPy;
cout << "Enter the size of array" << endl;
cin >> size;
cout << "Enter array elements" << endl;
int a[size];
for (int i = 0; i < size; i++) {
// Initializing array
cin >> a[i];
}
isPy = pyTriplet(a, size);
if (isPy) {
// If pyTriplet returns true.
cout << "Pythagorean Triplet Present" << endl;
}
else{
// If pyTriplet returns false
cout << "Pythagorean Triplet is not Present" << endl;
}
return 0;
}

Input

Enter the size of array 6
Enter array elements 1 5 21 23 29

Output

Implementation in Java

// Java code to find Pythagorean Triplet in an array.
import java.io.*;
import java.util.*;
class Main {
public static boolean pyTriplet(int a[], int size) {
// Square each element of the array and updating the given array.
for (int i = 0; i < size; i++) {
a[i] = a[i] * a[i];
}
// Sorting
Arrays.sort(a);
/* Fix one element and find remaining two.
This loop will start from the end of the array.*/
for (int i = size - 1; i >= 2; i--) {
// Index of first element.
int low = 0;
// Index of last element
int high = i - 1;
while (low < high) {
// Return true if Pythagorean Triplet is found
if (a[low] + a[high] == a[i]) {
return true;
}
// Otherwise move either high or low
if (a[low] + a[high] < a[i]) {
low++;
}
else {
high--;
}
}
}
// Return false if Pythagorean Triplet is not found
return false;
}
// Main code
public static void main(String args[]) {
int size;
boolean isPy;
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of the array");
size = sc.nextInt();
int a[] = new int[size];
System.out.println("Enter the elements of the array");
for (int i = 0; i < size; i++) {
// Populating the array
a[i] = sc.nextInt();
}
// Function call
isPy = pyTriplet(a, size);
if (isPy) {
// If function returns true
System.out.println("Pythagorean Triplet present");
}
else {
// If function returns false
System.out.println("Pythagorean Triplet not present");
}
}
}

Input

Enter the size of array 6
Enter array elements 1 5 21 6 23 19

Output

Implementation in Python

# Python implementation to find Pythagorean Triplet in an array
def pyTriplet(a, size):
# Square array elements
for i in range(size):
a[i] = a[i] * a[i]
# Sorting
a.sort()
for i in range(size - 1, 1, -1):
low = 0
high = i - 1
while (low < high):
# Pythagorean Triplet present
if (a[low] + a[high] == a[i]):
return 1
else:
if (a[low] + a[high] < a[i]):
low = low + 1
else:
high = high - 1
# Pythagorean Triplet not found
return 0
# Main code
a = []
size = int(input("Enter size of array "))
print("enter the elements of the array")
# Populating the array
for i in range(0, size):
a_element = int(input())
a.append(a_element)
# Function call
isPy = pyTriplet(a, size)
if isPy == 1:
# If function returns 1.
print("Pythagorean Triplet Present")
else:
# If function returns 0.
print("Pythagorean Triplet not Present")

Input

Enter the size of array 6
Enter array elements 1 5 21 6 23 29

Output

Complexity

Time complexity

O(N^{2}), where N is the size of the array.

Reason: This method has an O(N^{2}) time complexity. It is because we are using two nested loops.

Space Complexity

O(1) is the space complexity.

Reason: The space complexity remains O(1) since we are not using any extra space.

Use of Hashing

One more solution to this problem is to use hashing. However, it will have little effect on the time complexity.

Algorithm

Store each element in the hash array.

We want to find three values p, q, and r such that p^{2} + q^{2} = r^{2}

Run a nested loop to test all possible p and q combinations, then check our hash array to see if the corresponding value of r is present or not.

If r is found, there exists a Pythagorean Triplet in an array. Hence, return true. If r is not found, return false.

Implementation in C++

// C++ implementation to find Pythagorean Triplet in an array
#include <bits/stdc++.h>
using namespace std;
bool pyTriplet(int a[], int size) {
int maxi = 0;
for (int i = 0; i < size; i++) {
maxi = max(maxi, a[i]);
}
int hash_array[maxi + 1] = {0};
/*
Increment the value of hash array where index = input array element
*/
for (int i = 0; i < size; i++) {
hash_array[a[i]]++;
}
// Looping for all p
for (int i = 1; i < maxi + 1; i++) {
if (hash_array[i] == 0) {
continue;
}
// Looping for all possible q
for (int j = 1; j < maxi + 1; j++) {
if ((i == j && hash_array[i] == 1) || hash_array[j] == 0) {
continue;
}
int r = sqrt(i * i + j * j);
if ((r * r) != (i * i + j * j)) {
continue;
}
if (r > maxi) {
continue;
}
/*
If r is present in original array, Pythagorean Triplet is found
*/
if (hash_array[r]) {
return true;
}
}
}
// Pythagorean Triplet not found
return false;
}
// Main code
int main() {
int size;
bool isPy;
cout << "Enter the size of array" << endl;
cin >> size;
cout << "Enter array elements" << endl;
int a[size];
for (int i = 0; i < size; i++) {
// Initializing array
cin >> a[i];
}
isPy = pyTriplet(a, size);
if (isPy) {
// If pyTriplet returns true
cout << "Pythagorean Triplet Present" << endl;
}
else {
// If pyTriplet returns false
cout << "Pythagorean Triplet is not Present" << endl;
}
return 0;
}

Input

Enter the size of array 7
Enter array elements 1 3 5 7 4 7 19

Output

Implementation in Java

import java.util.*;
class Main {
public static boolean pyTriplet(int a[], int size) {
// Finding maximum element
int maxi = 0;
for (int i = 0; i < size; i++) {
maxi = Math.max(maxi, a[i]);
}
// Hashing_array
int hash_array[] = new int[maxi + 1];
/* Increment the value of hash array
Where index = input array element*/
for (int i = 0; i < size; i++) {
hash_array[a[i]]++;
}
// Looping for all p
for (int i = 1; i < maxi + 1; i++) {
if (hash_array[i] == 0) {
continue;
}
// Looping for all q
for (int j = 1; j < maxi + 1; j++) {
if ((i == j && hash_array[i] == 1) || hash_array[j] == 0) {
continue;
}
// Finding r
int r = (int) Math.sqrt(i * i + j * j);
if ((r * r) != (i * i + j * j)) {
continue;
}
if (r > maxi) {
continue;
}
/* If r is present in original array,
Pythagorean Triplet is found*/
if (hash_array[r] == 1) {
return true;
}
}
}
// Pythagorean Triplet not found
return false;
}
// Main code
public static void main(String args[]) {
int size;
boolean isPy;
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of the array");
size = sc.nextInt();
int a[] = new int[size];
System.out.println("Enter the elements of the array");
for (int i = 0; i < size; i++) {
// Populating the array
a[i] = sc.nextInt();
}
// Function call
isPy = pyTriplet(a, size);
if (isPy) {
// If function returns true
System.out.println("Pythagorean Triplet present");
}
else {
// If function returns false
System.out.println("Pythagorean Triplet not present");
}
}
}

Input

Enter the size of the array 7
Enter array elements 1 3 5 7 4 7 19

Output

Implementation in Python

# Python code to find Pythagorean Triplet in an array
import math
def pyTriplet(a, size):
maxi = 0
# Maximum element from the array
maxi = max(a)
# Creating Hash array
hash = [0] * (maxi + 1)
for i in range(size):
hash[a[i]] += 1
# Looping for all p
for i in range(1, maxi + 1):
# If p is not present
if hash[i] == 0:
continue
# Looping for all q
for j in range(1, maxi + 1):
if i == j and hash[i] == 1:
# If p and q are equal and there exists only one p.
continue
if hash[j] == 0:
# Or if q does not exist in the input array.
continue
# Finding r
r = int(math.sqrt(i * i + j * j))
# If r^2 isn't perfect square.
if (r * r) != (i * i + j * j):
continue
# If r is more than maximum value.
if r > maxi:
continue
# If r is in the original array, Triplet is found.
if hash[r]:
return True
return False
# Main code
a = []
size = int(input("Enter size of array "))
print("enter the elements of the array")
# Populating the array
for i in range(0, size):
a_element = int(input())
a.append(a_element)
# Function call
isPy = pyTriplet(a, size)
if isPy == 1:
# If function returns 1
print("Pythagorean Triplet Present")
else:
# If function returns 0
print("Pythagorean Triplet not Present")

Input

Enter the size of array 7
Enter array elements 1 3 5 7 4 7 19

Output

Complexity

Time Complexity

O(maxi*maxi),where, the maxi is the maximum element of the array.

Reason: This approach has a time complexity of O(maxi*maxi). It is because we are using two nested loops.

Space Complexity

O(maxi), where the maxi is the maximum element of the array.

Reason: Since we are using extra space equal to the maximum element, the space complexity becomes O(maxi).

Frequently Asked Questions

What is Hashing?

Hashing is a technique or process that uses a hash function to map pairs of keys and values into a hash table.

What is a Pythagorean Triplet?

Any three numbers that satisfy the Pythagoras theorem are called Pythagorean Triplets. If three numbers p, q, and r satisfy the relation p^{2} + q^{2} = r^{2}, they are said to be Pythagorean Triplets.

What is an array?

An array is a group of elements of a similar data type that are referenced by a common name.

What is time complexity?

The amount of time an algorithm or code takes to execute each instruction is known as its time complexity.

What is space complexity?

The total memory space used by an algorithm or a code, including the space of input values, is referred to as "space complexity."

Conclusion

We understood the problem of finding Pythagorean Triplets in an array. We also implemented the code in different languages.

We hope this article helps you on your journey. You can look at these array-related questions. It will help you understand arrays better!