Count of acute, obtuse and right triangles with given sides
Given an array of n positive distinct integers representing lengths of lines that can form a triangle. The task is to find the number of acute triangles, obtuse triangles, and right triangles separately that can be formed from the given array.
Examples:
Input : arr[] = { 2, 3, 9, 10, 12, 15 }. Output : Acute Triangle: 2 Right Triangle: 1 Obtuse Triangle: 4 Acute triangles that can be formed are {10, 12, 15} and { 9, 10, 12 }. Right triangles that can be formed are {9, 12, 15}. Obtuse triangles that can be formed are {2, 9, 10}, {3, 9, 10}, {3, 10, 12} and {9, 10, 15}.
Triangle having edges a, b, c, a <= b c.
If a2 + b2 > c2, then it is acute triangle.
If a2 + b2 = c2, then it is right triangle.
If a2 + b2 < c2, then it is obtuse triangle.
Method 1 (Simple): A brute force can be, use three loops, one for each side. Check the above three conditions if a triangle is possible from three sides.
Method 2 (Efficient): An efficient approach is to first sort the array and run two loops for side a and b (a<b). Then find the farthest point q where a + b > c. So, from b to q all triangle are possible.
Also find a farthest point p where a2 + b2 >= c2.
Now, observe if a2 + b2 = c2, then increment count of right triangles. Also, the acute triangle will be p – b – 1, and the obtuse triangle will be q – p.
C++
// C++ program to count of acute, obtuse and right // triangles in an array #include <bits/stdc++.h> using namespace std; // Find the number of acute, right, obtuse triangle // that can be formed from given array. void findTriangle( int a[], int n) { int b[n + 2]; // Finding the square of each element of array. for ( int i = 0; i < n; i++) b[i] = a[i] * a[i]; // Sort the sides of array and their squares. sort(a, a + n); sort(b, b + n); // x for acute triangles // y for right triangles // z for obtuse triangles int x=0,y=0,z=0; for ( int i=0; i<n; i++) { int p = i+1; int q = i+1; for ( int j=i+1; j<n; j++) { // Finding the farthest point p where // a^2 + b^2 >= c^2. while (p<n-1 && b[i]+b[j]>=b[p+1]) p++; q = max(q, p); // Finding the farthest point q where // a + b > c. while (q<n-1 && a[i]+a[j]>a[q+1]) q++; // If point p make right triangle. if (b[i]+b[j]==b[p]) { // All triangle between j and p are acute // triangles. So add p - j - 1 in x. x += max(p - j - 1, 0); // Increment y by 1. y++; // All triangle between q and p are acute // triangles. So add q - p in z. z += q - p; } // If no right triangle else { // All triangle between j and p are acute // triangles. So add p - j in x. x += max(p - j, 0); // All triangle between q and p are acute // triangles. So add q - p in z. z += q - p; } } } cout << "Acute Triangle: " << x << endl; cout << "Right Triangle: " << y << endl; cout << "Obtuse Triangle: " << z << endl; } // Driver Code int main() { int arr[] = {2, 3, 9, 10, 12, 15}; int n = sizeof (arr)/ sizeof (arr[0]); findTriangle(arr, n); return 0; } |
Java
// Java program to count of // acute, obtuse and right // triangles in an array import java.util.*; class GFG{ // Find the number of acute, // right, obtuse triangle // that can be formed from // given array. static void findTriangle( int a[], int n) { int b[] = new int [n]; // Finding the square of // each element of array. for ( int i = 0 ; i < n; i++) b[i] = a[i] * a[i]; // Sort the sides of array // and their squares. Arrays.sort(a); Arrays.sort(b); // x for acute triangles // y for right triangles // z for obtuse triangles int x = 0 , y = 0 , z = 0 ; for ( int i = 0 ; i < n; i++) { int p = i + 1 ; int q = i + 1 ; for ( int j = i + 1 ; j < n; j++) { // Finding the farthest point // p where a^2 + b^2 >= c^2. while (p < n - 1 && b[i] + b[j] >= b[p + 1 ]) p++; q = Math.max(q, p); // Finding the farthest point // q where a + b > c. while (q < n - 1 && a[i] + a[j] > a[q + 1 ]) q++; // If point p make right triangle. if (b[i] + b[j] == b[p]) { // All triangle between j // and p are acute triangles. // So add p - j - 1 in x. x += Math.max(p - j - 1 , 0 ); // Increment y by 1. y++; // All triangle between q // and p are acute triangles. // So add q - p in z. z += q - p; } // If no right triangle else { // All triangle between // j and p are acute triangles. // So add p - j in x. x += Math.max(p - j, 0 ); // All triangle between q // and p are acute triangles. // So add q - p in z. z += q - p; } } } System.out.println( "Acute Triangle: " + x); System.out.println( "Right Triangle: " + y); System.out.println( "Obtuse Triangle: " + z); } // Driver Code public static void main(String[] args) { int arr[] = { 2 , 3 , 9 , 10 , 12 , 15 }; int n = arr.length; findTriangle(arr, n); } } // This code is contributed by Chitranayal |
Python3
# Python3 program to count of acute, obtuse and right # triangles in an array # Find the number of acute, right, obtuse triangle # that can be formed from given array. def findTriangle(a, n) : b = [] # Finding the square of each element of array for i in range (n) : b.append(a[i] * a[i]) # Sort the sides of array and their squares. a.sort() b.sort() # x for acute triangles # y for right triangles # z for obtuse triangles x, y, z = 0 , 0 , 0 for i in range (n) : p = i + 1 q = i + 1 for j in range (i + 1 , n) : # Finding the farthest point p where # a^2 + b^2 >= c^2. while (p<n - 1 and b[i] + b[j]> = b[p + 1 ]) : p + = 1 q = max (q, p) # Finding the farthest point q where # a + b > c. while (q<n - 1 and a[i] + a[j]>a[q + 1 ]) : q + = 1 # If point p make right triangle. if (b[i] + b[j] = = b[p]) : # All triangle between j and p are acute # triangles. So add p - j - 1 in x. x + = max (p - j - 1 , 0 ) # Increment y by 1. y + = 1 # All triangle between q and p are acute # triangles. So add q - p in z. z + = q - p # If no right triangle else : # All triangle between j and p are acute # triangles. So add p - j in x. x + = max (p - j, 0 ) # All triangle between q and p are acute # triangles. So add q - p in z. z + = q - p print ( "Acute Triangle:" ,x ) print ( "Right Triangle:" , y) print ( "Obtuse Triangle:" , z) # Driver Code if __name__ = = "__main__" : arr = [ 2 , 3 , 9 , 10 , 12 , 15 ] n = len (arr) findTriangle(arr, n) # This code is contributed by Ryuga |
C#
// C# program to count of // acute, obtuse and right // triangles in an array using System; class GFG{ // Find the number of acute, // right, obtuse triangle // that can be formed from // given array. static void findTriangle( int []a, int n) { int []b = new int [n]; // Finding the square of // each element of array. for ( int i = 0; i < n; i++) b[i] = a[i] * a[i]; // Sort the sides of array // and their squares. Array.Sort(a); Array.Sort(b); // x for acute triangles // y for right triangles // z for obtuse triangles int x = 0, y = 0, z = 0; for ( int i = 0; i < n; i++) { int p = i + 1; int q = i + 1; for ( int j = i + 1; j < n; j++) { // Finding the farthest point // p where a^2 + b^2 >= c^2. while (p < n - 1 && b[i] + b[j] >= b[p + 1]) p++; q = Math.Max(q, p); // Finding the farthest point // q where a + b > c. while (q < n - 1 && a[i] + a[j] > a[q + 1]) q++; // If point p make right triangle. if (b[i] + b[j] == b[p]) { // All triangle between j // and p are acute triangles. // So add p - j - 1 in x. x += Math.Max(p - j - 1, 0); // Increment y by 1. y++; // All triangle between q // and p are acute triangles. // So add q - p in z. z += q - p; } // If no right triangle else { // All triangle between // j and p are acute triangles. // So add p - j in x. x += Math.Max(p - j, 0); // All triangle between q // and p are acute triangles. // So add q - p in z. z += q - p; } } } Console.Write( "Acute Triangle: " + x + "\n" ); Console.Write( "Right Triangle: " + y + "\n" ); Console.Write( "Obtuse Triangle: " + z + "\n" ); } // Driver Code public static void Main( string [] args) { int []arr = { 2, 3, 9, 10, 12, 15 }; int n = arr.Length; findTriangle(arr, n); } } // This code is contributed by rutvik_56 |
PHP
<?php // PHP program to count of acute, obtuse // and right triangles in an array // Find the number of acute, right, obtuse // triangle that can be formed from given array. function findTriangle( $a , $n ) { $b [ $n + 2] = array (); // Finding the square of each // element of array. for ( $i = 0; $i < $n ; $i ++) $b [ $i ] = $a [ $i ] * $a [ $i ]; // Sort the sides of array and // their squares. sort( $a ); sort( $b ); // x for acute triangles // y for right triangles // z for obtuse triangles $x = 0; $y = 0; $z = 0; for ( $i = 0; $i < $n ; $i ++) { $p = $i + 1; $q = $i + 1; for ( $j = $i + 1; $j < $n ; $j ++) { // Finding the farthest point p // where a^2 + b^2 >= c^2. while ( $p < $n - 1 && $b [ $i ] + $b [ $j ] >= $b [ $p + 1]) $p ++; $q = max( $q , $p ); // Finding the farthest point q // where a + b > c. while ( $q < $n - 1 && $a [ $i ] + $a [ $j ] > $a [ $q + 1]) $q ++; // If point p make right triangle. if ( $b [ $i ] + $b [ $j ] == $b [ $p ]) { // All triangle between j and p are acute // triangles. So add p - j - 1 in x. $x += max( $p - $j - 1, 0); // Increment y by 1. $y ++; // All triangle between q and p are // acute triangles. So add q - p in z. $z += $q - $p ; } // If no right triangle else { // All triangle between j and p are acute // triangles. So add p - j in x. $x += max( $p - $j , 0); // All triangle between q and p are acute // triangles. So add q - p in z. $z += $q - $p ; } } } echo "Acute Triangle: " , $x , "\n" ; echo "Right Triangle: " , $y , "\n" ; echo "Obtuse Triangle: " , $z , "\n" ; } // Driver Code $arr = array (2, 3, 9, 10, 12, 15); $n = sizeof( $arr ); findTriangle( $arr , $n ); // This code is contributed by akt_mit ?> |
Javascript
<script> // Javascript program to count of // acute, obtuse and right // triangles in an array // Find the number of acute, // right, obtuse triangle // that can be formed from // given array. function findTriangle(a,n) { let b= new Array(n); for (let i=0;i<n;i++) { b[i]=0; } // Finding the square of // each element of array. for (let i = 0; i < n; i++) b[i] = a[i] * a[i]; // Sort the sides of array // and their squares. a.sort( function (i,j){ return i-j;}); b.sort( function (i,j){ return i-j;}); // x for acute triangles // y for right triangles // z for obtuse triangles let x = 0, y = 0, z = 0; for (let i = 0; i < n; i++) { let p = i + 1; let q = i + 1; for (let j = i + 1; j < n; j++) { // Finding the farthest point // p where a^2 + b^2 >= c^2. while (p < n - 1 && b[i] + b[j] >= b[p + 1]) p++; q = Math.max(q, p); // Finding the farthest point // q where a + b > c. while (q < n - 1 && a[i] + a[j] > a[q + 1]) q++; // If point p make right triangle. if (b[i] + b[j] == b[p]) { // All triangle between j // and p are acute triangles. // So add p - j - 1 in x. x += Math.max(p - j - 1, 0); // Increment y by 1. y++; // All triangle between q // and p are acute triangles. // So add q - p in z. z += q - p; } // If no right triangle else { // All triangle between // j and p are acute triangles. // So add p - j in x. x += Math.max(p - j, 0); // All triangle between q // and p are acute triangles. // So add q - p in z. z += q - p; } } } document.write( "Acute Triangle: " + x+ "<br>" ); document.write( "Right Triangle: " + y+ "<br>" ); document.write( "Obtuse Triangle: " + z+ "<br>" ); } // Driver Code let arr=[2, 3, 9, 10, 12, 15]; let n = arr.length; findTriangle(arr, n); // This code is contributed by avanitrachhadiya2155 </script> |
Output:
Acute Triangle: 2 Right Triangle: 1 Obtuse Triangle: 4
Time Complexity: O(n^3), as in the worst case we are iterating through three loops up to n.
Auxiliary Space: O(n)