How do you find the triplet of an array in python?

Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a2 + b2 = c2.

Example: 

Input: arr[] = {3, 1, 4, 6, 5} 
Output: True 
There is a Pythagorean triplet (3, 4, 5).

Input: arr[] = {10, 4, 6, 12, 5} 
Output: False 
There is no Pythagorean triplet. 

Method 1 (Naive) 
A simple solution is to run three loops, three loops pick three array elements, and check if the current three elements form a Pythagorean Triplet. 

Below is the implementation of the above idea :

C++

#include

using namespace std;

bool isTriplet(int ar[], int n)

{

    for (int i = 0; i < n; i++) {

        for (int j = i + 1; j < n; j++) {

            for (int k = j + 1; k < n; k++) {

                int x = ar[i] * ar[i], y = ar[j] * ar[j], z = ar[k] * ar[k];

                if (x == y + z || y == x + z || z == x + y)

                    return true;

            }

        }

    }

    return false;

}

int main()

{

    int ar[] = { 3, 1, 4, 6, 5 };

    int ar_size = sizeof(ar) / sizeof(ar[0]);

    isTriplet(ar, ar_size) ? cout << "Yes" : cout << "No";

    return 0;

}

Java

import java.io.*;

class PythagoreanTriplet {

    static boolean isTriplet(int ar[], int n)

    {

        for (int i = 0; i < n; i++) {

            for (int j = i + 1; j < n; j++) {

                for (int k = j + 1; k < n; k++) {

                    int x = ar[i] * ar[i], y = ar[j] * ar[j], z = ar[k] * ar[k];

                    if (x == y + z || y == x + z || z == x + y)

                        return true;

                }

            }

        }

        return false;

    }

    public static void main(String[] args)

    {

        int ar[] = { 3, 1, 4, 6, 5 };

        int ar_size = ar.length;

        if (isTriplet(ar, ar_size) == true)

            System.out.println("Yes");

        else

            System.out.println("No");

    }

}

Python3

def isTriplet(ar, n):

    j = 0

    for i in range(n - 2):

        for j in range(i + 1, n):

            for k in range(j + 1, n - 1):

                x = ar[i]*ar[i]

                y = ar[j]*ar[j]

                z = ar[k]*ar[k]

                if (x == y + z or y == x + z or z == x + y):

                    return 1

    return 0

ar = [3, 1, 4, 6, 5]

ar_size = len(ar)

if(isTriplet(ar, ar_size)):

    print("Yes")

else:

    print("No")

C#

using System;

class GFG {

    static bool isTriplet(int[] ar, int n)

    {

        for (int i = 0; i < n; i++) {

            for (int j = i + 1; j < n; j++) {

                for (int k = j + 1; k < n; k++) {

                    int x = ar[i] * ar[i], y = ar[j] * ar[j], z = ar[k] * ar[k];

                    if (x == y + z || y == x + z || z == x + y)

                        return true;

                }

            }

        }

        return false;

    }

    public static void Main()

    {

        int[] ar = { 3, 1, 4, 6, 5 };

        int ar_size = ar.Length;

        if (isTriplet(ar, ar_size) == true)

            Console.WriteLine("Yes");

        else

            Console.WriteLine("No");

    }

}

PHP

function isTriplet($ar, $n)

{

    for ($i = 0; $i < $n; $i++)

    {

    for ($j = $i + 1; $j < $n; $j++)

    {

        for ($k = $j + 1; $k < $n; $k++)

        {

            $x = $ar[$i] * $ar[$i];

            $y = $ar[$j] * $ar[$j];

            $z = $ar[$k] * $ar[$k];

            if ($x == $y + $z or

                $y == $x + $z or

                $z == $x + $y)

                return true;

        }

    }

    }

    return false;

}

    $ar = array(3, 1, 4, 6, 5);

    $ar_size = count($ar);

    if(isTriplet($ar, $ar_size))

        echo "Yes";

    else

        echo "No";

?>

Javascript

Output: 

Yes

The Time Complexity of the above solution is O(n3). 

Auxiliary Space: O(1)

Method 2 (Use Sorting) 
We can solve this in O(n2) time by sorting the array first. 
1) Do the square of every element in the input array. This step takes O(n) time.
2) Sort the squared array in increasing order. This step takes O(nLogn) time.
3) To find a triplet (a, b, c) such that a2 = b2 + c2, do following. 

1. Fix ‘a’ as the last element of the sorted array.
2. Now search for pair (b, c) in subarray between the first element and ‘a’. A pair (b, c) with a given sum can be found in O(n) time using the meet in middle algorithm discussed in method 1 of this post.
3. If no pair is found for current ‘a’, then move ‘a’ one position back and repeat step 3.2.

Below image is a dry run of the above approach: 

Below is the implementation of the above approach: 

C++

#include

#include

using namespace std;

bool isTriplet(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        arr[i] = arr[i] * arr[i];

    sort(arr, arr + n);

    for (int i = n - 1; i >= 2; i--) {

        int l = 0;

        int r = i - 1;

        while (l < r) {

            if (arr[l] + arr[r] == arr[i])

                return true;

            (arr[l] + arr[r] < arr[i]) ? l++ : r--;

        }

    }

    return false;

}

int main()

{

    int arr[] = { 3, 1, 4, 6, 5 };

    int arr_size = sizeof(arr) / sizeof(arr[0]);

    isTriplet(arr, arr_size) ? cout << "Yes" : cout << "No";

    return 0;

}

Java

import java.io.*;

import java.util.*;

class PythagoreanTriplet {

    static boolean isTriplet(int arr[], int n)

    {

        for (int i = 0; i < n; i++)

            arr[i] = arr[i] * arr[i];

        Arrays.sort(arr);

        for (int i = n - 1; i >= 2; i--) {

            int l = 0;

            int r = i - 1;

            while (l < r) {

                if (arr[l] + arr[r] == arr[i])

                    return true;

                if (arr[l] + arr[r] < arr[i])

                    l++;

                else

                    r--;

            }

        }

        return false;

    }

    public static void main(String[] args)

    {

        int arr[] = { 3, 1, 4, 6, 5 };

        int arr_size = arr.length;

        if (isTriplet(arr, arr_size) == true)

            System.out.println("Yes");

        else

            System.out.println("No");

    }

}

 Yes