Count the number of possible triangles | Function to count all possible triangles with arr [ ] element ; 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 code
< ? php function findNumberOfTriangles ( $ arr ) { $ n = count ( $ arr ) ; sort ( $ arr ) ; $ count = 0 ; for ( $ i = 0 ; $ i < $ n - 2 ; ++ $ i ) { $ k = $ i + 2 ; for ( $ 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 ; } $ arr = array ( 10 , 21 , 22 , 100 , 101 , 200 , 300 ) ; echo " Total ▁ number ▁ of ▁ triangles ▁ is ▁ " , findNumberOfTriangles ( $ arr ) ; ? >