# Find pythagorean triplet in an unsorted array in java

285 views

Find pythagorean triplet in an unsorted array in java ?

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

Output:-

[3, 4, 5]

Pythagorean: true

by (3.7k points)

As we know that in simple math about the pythagorean as look like:- a2 + b2 = c2.

A very simple solution to find pythagorean triplet. Run three loops and pick three array elements and check if current three elements form a Pythagorean Triplet. If found the print otherwise print not found.

This solution will take O(n^3) time complexity.

public static void main(String[] args) {
int arr[] = {3, 1, 4, 6, 5};
boolean isPythagorean = isPythagoreanTriplet(arr);
System.out.println("Pythagorean: " + isPythagorean);
}

//Time Complexity:- O(n^3).
private static boolean isPythagoreanTriplet(int[] arr) {
for(int i=0;i<arr.length; i++) {
for(int j=i+1; j<arr.length; j++) {
for(int k=j+1; k<arr.length; k++) {
if(((arr[i]*arr[i])+(arr[j]*arr[j]))==(arr[k]*arr[k])) {
System.out.println("["+arr[i]+", "+arr[j]+", "+arr[k]+"]");
return true;
}
}
}
}
return false;
}

Output:-

[3, 4, 5]
Pythagorean: true

by (4.4k points)

To find pythagorean triplet in unsorted array. See the solution is better way with O(n^2) time complexity using sorting

public static void main(String[] args) {

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

isPythagorean = isPythagoreanTripletUsingSorting(arr);

System.out.println("Pythagorean: " + isPythagorean);

}

//Time complexity:- O(n^2)

private static boolean isPythagoreanTripletUsingSorting(int[] arr) {

// Square array elements

for (int i = 0; i < arr.length; i++)

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

// Sort array elements

Arrays.sort(arr);

// Now fix one element one by one and find the other two

// elements

for (int i = arr.length - 1; i >= 2; i--) {

// To find the other two elements, start two index

// variables from two corners of the array and move

// them toward each other

int start = 0; // index of the first element in arr[0..i-1]

int end = i - 1; // index of the last element in arr[0..i-1]

while (start < end) {

// A triplet found

if (arr[start] + arr[end] == arr[i]) {

System.out.println("["+Math.sqrt(arr[start])+", "+Math.sqrt(arr[end])+", "+Math.sqrt(arr[i])+"]");

return true;

}

// Else either move 'l' or 'r'

if (arr[start] + arr[end] < arr[i])

start++;

else

end--;

}

}

return false;

}