Pythagoreon Triplet Efficient Code
In this class, We discuss Pythagorean Triplet Efficient Code.
The reader can take the complete competitive coding course for the product development company. Click Here.
For Complete YouTube Video: Click Here
Question:
First, we understand the Pythagorean triplet.
From the Pythagoras theorem a^2 + b^2 = c^2
Take the elements 3, 4 and 5. 3^2 + 4^2 = 5^2
The triplets 3, 4 and 5 we call Pythagorean triplets.
Given a list of elements, do we need to identify whether the Pythagorean triplet exists or not?
Example:
3, 2, 4, 6, and 5 are on the list.
The above list contains a Pythagorean triplet.
Time complexity = O(n^2)
Space complexity = O(n)
One way:
Find all the combinations of triplets from the given list.
To identify triplet from the list, we need to use a three-level nested loop.
Find each triplet and check the triplet matches the Pythagoras equation.
The time complexity for finding a triplet is O(n^3).
Second way:
Square the elements and sort them in ascending order.
The below diagram shows the elements and the procedure to find triplets.
Step by step explanation is provided in the above video.
Code:
class Solution:
def checkTriplet(self,arr, n):
for i in range(n):
arr[i] = arr[i] * arr[i]
arr.sort()
for i in range(n-1, 1, -1):
j = 0
k = i – 1
while (j < k):
if (arr[j] + arr[k] == arr[i]):
return True
else:
if (arr[j] + arr[k] < arr[i]):
j = j + 1
else:
k = k – 1
return False
print(“enter n value”)
n= int(input())
print(“give n positive integers”)
arr=list(map(int,input().strip().split()))
ob = Solution()
if(ob.checkTriplet(arr,n) == True):
print(“yes”)
else:
print(“false”)