WAP For Find Maximum Possible Combinations Of Triangle

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 create 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

Alternative Way 1:

This Java program calculates the total number of triangles that can be formed from a given array of integers. To create 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 and sorts it. It 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

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 create 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

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 and sorts it, 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