Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Array
3.
Pythagorean Triplets
4.
Problem Statement
5.
Explanation with Example
6.
Brute-Force Approach
6.1.
Algorithm
6.2.
Implementation in C++
6.2.1.
Input
6.2.2.
Output
6.3.
Implementation in Java
6.3.1.
Input
6.3.2.
Output
6.4.
Implementation in Python
6.4.1.
Input
6.4.2.
Output
7.
Complexity
7.1.
Time Complexity
7.2.
Space Complexity
8.
Use of Sorting
8.1.
Algorithm
8.2.
Implementation in C++
8.2.1.
Input
8.2.2.
Output
8.3.
Implementation in Java
8.3.1.
Input
8.3.2.
Output
8.4.
Implementation in Python
8.4.1.
Input
8.4.2.
Output
9.
Complexity
9.1.
Time complexity
9.2.
Space Complexity
10.
Use of Hashing
10.1.
Algorithm
10.2.
Implementation in C++
10.2.1.
Input
10.2.2.
Output
10.3.
Implementation in Java
10.3.1.
Input
10.3.2.
Output
10.4.
Implementation in Python
10.4.1.
Input
10.4.2.
Output
11.
Complexity
11.1.
Time Complexity
11.2.
Space Complexity
12.
Frequently Asked Questions
12.1.
What is Hashing?
12.2.
What is a Pythagorean Triplet?
12.3.
What is an array?
12.4.
What is time complexity?
12.5.
What is space complexity?
13.
Conclusion
Last Updated: Mar 27, 2024
Medium

Pythagorean Triplet in an Array

Author Gaurangi Tyagi
2 upvotes
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

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. 

Introduction

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:

Array

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.

Pythagorean Triplets

In simple words, if three numbers p, q, and r satisfy the relation p2 + q2 = r2, 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 p2 + q2 = r2

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.

Explanation with Example

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:

  1. Run three nested loops to pick three elements, p, q, and r, from the input array.
     
  2. If for any value of p, q, r,  the condition p2 = q2 + r2 is satisfied, our function will return true.
     
  3. Else our function will return false.
Brute-Force Approach

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

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

Output

Output

Also see, Morris Traversal for Inorder and  Rabin Karp Algorithm

Implementation in Python

# 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

Output

Complexity

Time Complexity

O(N3), 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(N3). 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

  1. Square each element of the input array ( a[ ] ).
     
  2. Sort the squared array in ascending order.
     
  3. To find a Pythagorean Triplet (p, q, r) where p = q + r, do the following:
    1. Fix ‘p' as the last element of your sorted array.
       
    2. Initialize ‘q’ as the first element and r as the second last (p-1) element of the sorted array.
       
    3. A Triplet is found if a[q] + a[r] = a[p]. 
       
    4. Otherwise, if a[q] + a[r] < a[p], increment q (i.e., q ++).
       
    5. Otherwise, if a[q] + a[r] > a[p], decrement r (i.e., r --).
       
    6. 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.
       
    7. Repeat steps b through until a Pythagorean Triplet is found or p reaches the second index.
Sorting Explanation 1
Sorting Explanation 2

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

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

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

output

Complexity

Time complexity

O(N2), where N is the size of the array.

Reason: This method has an O(N2) 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 p2 + q2 = r2
     
  • 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

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

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

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 p2 + q2 = r2, 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!

Recommended problems -

 

You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingSystem Design, and many more!

Head to our practice platform, Coding Ninjas Studio, to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more!

Happy coding, Ninja!

Previous article
Equilibrium Index of an Array
Next article
Javascript Program for Largest Sum Contiguous Subarray
Live masterclass