Maximum Possible Combinations Of Triangle: This Java program calculates the total number of triangles that can be formed from a given array of integers. To form a triangle, the sum of the lengths of any two sides must be greater than the length of the third side. The program takes an array of integers as input, sorts it, and then counts the number of valid triangles using a nested loop approach.
Maximum Possible Combinations Of Triangle
package com.softwaretestingo.interviewprograms;
import java.util.Arrays;
public class InterviewPrograms84
{
static int countTriangles(int[] arr, int n)
{
// atleast 3 numbers are required for a triangle.
if(n<3) return 0;
// Sort the array
Arrays.sort(arr);
int count = 0;
int i = 0;
int j = i+1;
while(i<n-2)
{
int k = j+1;
while(k<n && arr[k] < arr[i] + arr[j])
k++;
count += k-j-1;
j++;
// If j has reached the end. then reset both i & j.
if(j>=n)
{
i++;
j = i+1;
}
}
return count;
}
public static void main(String[] args)
{
int arr[] = { 10, 21, 22, 100, 101, 200, 300 };
int size = arr.length;
// Function call
System.out.println("Total number of triangles possible is "+ countTriangles(arr, size));
}
}
Output
Total number of triangles possible is 6
Let’s break down the program step by step to understand what it does:
- The program defines a class named InterviewPrograms84.
- Inside the class, there are two methods: countTriangles and main.
- The countTriangles method takes two parameters: an integer array arr and an integer n representing the size of the array. This method calculates and returns the total number of triangles that can be formed from the array elements.
- The first step in the method is to check if the size of the array n is less than 3 because at least three numbers are required to form a triangle. If n is less than 3, the method returns 0, indicating that no triangles can be formed.
- The array arr is sorted in ascending order using Arrays.sort(arr). Sorting the array is necessary to perform the triangle counting efficiently.
- The method initializes the variable count to 0, which will be used to store the total count of valid triangles.
- The method uses three pointers i, j, and k to traverse the array. The i pointer starts from index 0, the j pointer starts from index i+1, and the k pointer starts from index j+1.
- The method enters a nested loop where the outer loop runs until i reaches n-2. The nested loop keeps moving the k pointer until it reaches the end of the array or the condition arr[k] < arr[i] + arr[j] becomes false. The condition arr[k] < arr[i] + arr[j] checks if the triplet (arr[i], arr[j], arr[k]) can form a valid triangle.
- Inside the nested loop, the method increments the count variable by k-j-1, where k-j-1 represents the number of triangles that can be formed using the current i and j pointers.
- After the nested loop, the j pointer is incremented, and if it reaches the end of the array or goes beyond it (j>=n), the i pointer is incremented, and j is reset to i+1.
- The method repeats the process of moving k until it reaches the end of the array or the triangle condition becomes false, and the count of triangles is calculated in this manner.
- Finally, the method returns the total count of valid triangles.
- In the main method, an array of integers arr is created and initialized with the values {10, 21, 22, 100, 101, 200, 300}.
- The program calculates the total number of triangles that can be formed from the array using the countTriangles method and prints the result.
In summary, the program efficiently counts the total number of triangles that can be formed from an array of integers using the given conditions. The algorithm avoids redundant checks and achieves the task with time complexity O(n^2), making it efficient for larger arrays.
Alternative Way 1:
This Java program calculates the total number of triangles that can be formed from a given array of integers. To form a triangle, the sum of the lengths of any two sides must be greater than the length of the third side. The program takes an array of integers as input, sorts it, and then uses three nested loops to count the number of valid triangles based on the triangle inequality theorem.
package com.softwaretestingo.interviewprograms;
import java.util.Arrays;
public class InterviewPrograms84_1
{
//https://iq.opengenus.org/maximum-perimeter-of-triangle/
static int countTriangles(int[] arr, int n)
{
// Function to count all possible triangles with arr[]
// elements
// Sort the array
Arrays.sort(arr);
// Count of triangles
int count = 0;
// The three loops select three different values
// from array
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])
count++;
return count;
}
public static void main(String[] args)
{
int arr[] = { 10, 21, 22, 100, 101, 200, 300 };
int size = arr.length;
// Function call
System.out.println("Total number of triangles possible is "+ countTriangles(arr, size));
}
}
Output
Total number of triangles possible is 6
Let’s break down the program step by step to understand what it does:
- The program defines a class named InterviewPrograms84_1.
- Inside the class, there are two methods: countTriangles and main.
- The countTriangles method takes two parameters: an integer array arr and an integer n representing the size of the array. This method calculates and returns the total number of triangles that can be formed from the array elements.
- The array arr is sorted in ascending order using Arrays.sort(arr). Sorting the array is necessary to identify the longest side of the potential triangle in the nested loops efficiently.
- The method initializes the variable count to 0, which will be used to store the total count of valid triangles.
- The method uses three nested loops to select three different values from the array, denoted by the indices i, j, and k.
- The first loop (i loop) runs from 0 to n-1. The second loop (j loop) runs from i+1 to n-1. The third loop (k loop) runs from j+1 to n-1.
- Inside the nested loops, the program checks the triangle inequality theorem, which states that the sum of the lengths of any two sides of a triangle must be greater than the length of the third side. In this case, the condition arr[i] + arr[j] > arr[k] checks if the triplet (arr[i], arr[j], arr[k]) can form a valid triangle.
- If the condition arr[i] + arr[j] > arr[k] is true, it means that the triplet can form a valid triangle. The count variable is incremented, indicating that a valid triangle is found.
- After the nested loops finish, the count variable holds the total number of valid triangles that can be formed from the array elements.
- The method returns the total count of valid triangles.
- In the main method, an array of integers arr is created and initialized with the values {10, 21, 22, 100, 101, 200, 300}.
- The program calculates the total number of triangles that can be formed from the array using the countTriangles method and prints the result.
In summary, the program uses three nested loops to efficiently count the total number of triangles that can be formed from an array of integers based on the triangle inequality theorem. The algorithm avoids redundant checks and achieves the task with time complexity O(n^3), making it less efficient for larger arrays compared to the program in the previous example. However, for small arrays, this approach can be useful and straightforward to implement.
Alternative Way 2:
This Java program takes an array of integers as input and then finds and prints a set of three integers from the array that can form a valid triangle based on the triangle inequality theorem. To form a triangle, the sum of the lengths of any two sides must be greater than the length of the third side. The program first reads the size of the array and the elements from the user and then checks for a valid triangle by iterating through the sorted array from the largest side to the smallest side.
package com.softwaretestingo.interviewprograms;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class InterviewPrograms84_2
{
public static void main(String[] args) throws NumberFormatException, IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the Size Of The Array: ");
//no. of elements in array
int n = Integer.parseInt(br.readLine());
int[] sides = new int[n];
String[] input;
// Split Numbers Based On the Spaces
System.out.println("Enter the "+n +" Integers");
//input = br.readLine().split(" ");
for(int i=0; i<n; i++)
{
sides[i] = Integer.parseInt(br.readLine());
}
// Sort the array elements in non-decreasing order
Arrays.sort(sides);
boolean flag = false;
//starting from end, because we have sorted in
//ascending order and we want the max element
//first, you could also sort in descending order
//and start from i=0
for(int i=n-1; i>=2; i--)
{
if(sides[i-2]+sides[i-1]>sides[i])
{
System.out.println(sides[i-2]+" "+sides[i-1]+" "+sides[i]);
flag = true;
break;
}
}
if(flag==false)
{
System.out.println("-1");
}
}
}
Output
Enter the Size Of The Array: 5 Enter the 5 Integers 1 2 3 5 2 2 2 3
Let’s break down the program step by step to understand what it does:
- The program defines a class named InterviewPrograms84_2.
- Inside the class, there is the main method that handles the program logic.
- The main method uses a BufferedReader to read the size of the array (n) from the user.
- It initializes an integer array sides of size n to store the input elements.
- The program prompts the user to enter n integers one by one, and each integer is read using Integer.parseInt(br.readLine()) and stored in the sides array.
- The array elements in the sides array are then sorted in non-decreasing order using Arrays.sort(sides).
- A boolean variable flag is set to false. This variable will be used to check if a valid triangle is found or not.
- The program then starts a loop from the end of the array (largest side) towards the beginning (smallest side) using for(int i=n-1; i>=2; i–).
- Inside the loop, the program checks the triangle inequality theorem for the triplet (sides[i-2], sides[i-1], sides[i]). If sides[i-2] + sides[i-1] > sides[i], it means the triplet can form a valid triangle.
- If a valid triangle is found, the program prints the sides of the triangle using System.out.println(sides[i-2] + ” ” + sides[i-1] + ” ” + sides[i]), sets the flag variable to true, and breaks out of the loop using break;.
- After the loop finishes, the program checks the value of the flag variable. If flag is still false, it means no valid triangle was found, and it prints -1 to indicate that no valid triangle exists in the array.
In summary, the program efficiently finds and prints a set of three integers from the input array that can form a valid triangle based on the triangle inequality theorem. The program takes advantage of the fact that the largest side of the triangle must come at the end of the sorted array, which reduces the number of checks needed. The algorithm has a time complexity of O(nlogn) due to the sorting operation and O(n) for finding the valid triangle, making it efficient for large arrays.
Alternative Way 3:
This Java program finds and counts the number of possible triangles that can be formed from a given array of integers using the triangle inequality theorem. To form a triangle, the sum of the lengths of any two sides must be greater than the length of the third side. The program takes an array of integers as input, sorts it, and then efficiently calculates the count of possible triangles using a two-pointer approach.
package com.softwaretestingo.interviewprograms;
import java.util.Arrays;
public class InterviewPrograms84_3
{
static void CountTriangles(int[] A)
{
int n = A.length;
Arrays.sort(A);
int count = 0;
for (int i = n - 1; i >= 1; i--)
{
int l = 0, r = i - 1;
while (l < r)
{
if (A[l] + A[r] > A[i])
{
// If it is possible with a[l], a[r]
// and a[i] then it is also possible
// with a[l+1]..a[r-1], a[r] and a[i]
count += r - l;
// checking for more possible solutions
r--;
}
else // if not possible check for
// higher values of arr[l]
{
l++;
}
}
}
System.out.print("No of possible solutions: "+ count);
}
public static void main(String[] args)
{
int[] A = { 10, 21, 22, 100, 101, 200, 300 };
// Function call
CountTriangles(A);
}
}
Output
No of possible solutions: 6
Let’s break down the program step by step to understand what it does:
- The program defines a class named InterviewPrograms84_3.
- Inside the class, there are two methods: CountTriangles and main.
- The CountTriangles method takes an integer array A as input and calculates and prints the count of possible triangles that can be formed from the elements of the array.
- The program first determines the length of the array n using int n = A.length.
- The array A is then sorted in non-decreasing order using Arrays.sort(A).
- The method initializes a variable count to 0, which will be used to store the count of possible triangles.
- The program then enters a loop that starts from the end of the array (largest element) and goes towards the beginning.
- Inside the loop, the program uses two pointers l and r, initially set to 0 and i-1, respectively. The variable i is the current index of the loop.
- The loop checks the triangle inequality theorem for the triplet (A[l], A[r], A[i]). If A[l] + A[r] > A[i], it means the triplet can form a valid triangle.
- If a valid triangle is found, the program increments the count variable by r – l. This is because if the current triplet forms a valid triangle, then all the combinations of the left side (A[l]) with the right side (A[r]) and the largest side (A[i]) will also form valid triangles. Thus, we add r – l to the count to account for all such possible combinations.
- The program then checks for more possible solutions by decrementing the r pointer.
- If the current triplet does not form a valid triangle, the program increments the l pointer to check for higher values of A[l].
- The loop continues until l is less than r.
- After the loop finishes, the method prints the count of possible solutions using System.out.print(“No of possible solutions: ” + count);.
- In the main method, an array of integers A is created and initialized with the values {10, 21, 22, 100, 101, 200, 300}.
- The program calculates the count of possible triangles that can be formed from the array using the CountTriangles method and prints the result.
In summary, the program efficiently finds and counts the number of possible triangles that can be formed from an array of integers using the triangle inequality theorem. The algorithm uses a two-pointer approach to explore all possible combinations of sides and has a time complexity of O(n^2), making it efficient for larger arrays.
