text: Count the number of possible triangles | C program to count number of triangles that can be formed from given array ; Following function is needed for library function qsort ( ) . Refer www . cplusplus . com / reference / clibrary / cstdlib / qsort / ; Function to count all possible triangles with arr [ ] elements ; Sort the array elements in non - decreasing order ; Initialize count of triangles ; Fix the first element . We need to run till n - 3 as the other two elements are selected from arr [ i + 1. . . n - 1 ] ; Initialize index of the rightmost third element ; Fix the second element ; Find the rightmost element which is smaller than the sum of two fixed elements The important thing to note here is , we use the previous value of k . If value of arr [ i ] + arr [ j - 1 ] was greater than arr [ k ] , then arr [ i ] + arr [ j ] must be greater than k , because the array is sorted . ; Total number of possible triangles that can be formed with the two fixed elements is k - j - 1. The two fixed elements are arr [ i ] and arr [ j ] . All elements between arr [ j + 1 ] / to arr [ k - 1 ] can form a triangle with arr [ i ] and arr [ j ] . One is subtracted from k because k is incremented one extra in above while loop . k will always be greater than j . If j becomes equal to k , then above loop will increment k , because arr [ k ] + arr [ i ] is always greater than arr [ k ] ; Driver program to test above functionarr [ j + 1 ]
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE http : int comp ( const void * a , const void * b ) { return * ( int * ) a > * ( int * ) b ; } int findNumberOfTriangles ( int arr [ ] , int n ) { qsort ( arr , n , sizeof ( arr [ 0 ] ) , comp ) ; int count = 0 ; for ( int i = 0 ; i < n - 2 ; ++ i ) { int k = i + 2 ; for ( int j = i + 1 ; j < n ; ++ j ) { while ( k < n && arr [ i ] + arr [ j ] > arr [ k ] ) ++ k ; if ( k > j ) count += k - j - 1 ; } } return count ; } int main ( ) { int arr [ ] = { 10 , 21 , 22 , 100 , 101 , 200 , 300 } ; int size = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printf ( " Total ▁ number ▁ of ▁ triangles ▁ possible ▁ is ▁ % d ▁ " , findNumberOfTriangles ( arr , size ) ) ; return 0 ; }