In this example, we’ll find possible triangles in an array:
Input:
int[] arr1 = {4, 3, 9, 8 };
Output:
Set 1 :: 4 9 8
Set 2 :: 3 9 8
Possible triangles :: 2
Algorithm: (Approach #1)
- Run three nested loops, each loop starting from the index of the previous loop to end of the array.
- Check if sum of two sides is greater than the third.
- If all three conditions match, (that means it is a possible triangle), then increase the count.
- Print the sides/count.
1. Java
public class FindPossibleTriangles {
public static void main(String[] args) {
int[] arr = {6, 4, 9, 7, 8};
int numberOfTriangles = findNumberOfTriangles(arr, arr.length);
System.out.println("Possible triangles :: " + numberOfTriangles);
}
static int findNumberOfTriangles(int arr[], int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (arr[i] + arr[j] > arr[k]
&& arr[i] + arr[k] > arr[j]
&& arr[k] + arr[j] > arr[i]) {
count++;
System.out.println("Set " + count + " :: " + arr[i] + " " + arr[j] + " " + arr[k]);
}
}
}
}
return count;
}
}
Output:
Set 1 :: 6 4 9
Set 2 :: 6 4 7
Set 3 :: 6 4 8
Set 4 :: 6 9 7
Set 5 :: 6 9 8
Set 6 :: 6 7 8
Set 7 :: 4 9 7
Set 8 :: 4 9 8
Set 9 :: 4 7 8
Set 10 :: 9 7 8
Possible triangles :: 10
Approach #2:
// Effective approach
static int findNumberOfTriangles(int arr[], int n) {
int count = 0;
Arrays.sort(arr);
for(int i= arr.length - 1; i >=0; i--){
int left = 0;
int right = i - 1;
while(left < right){
if(arr[left] + arr[right] > arr[i]){
count += (right - left);
right--;
}
else{
left++;
}
}
}
return count;
}
Complete Java Solutions can be found here: Github Link