Count the number of possible triangles | Function to count all possible triangles with arr [ ] elements ; Sort array and initialize count as 0 ; 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 function to test above function
def findnumberofTriangles ( arr ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE arr . sort ( ) NEW_LINE count = 0 NEW_LINE for i in range ( 0 , n - 2 ) : NEW_LINE INDENT k = i + 2 NEW_LINE for j in range ( i + 1 , n ) : NEW_LINE INDENT while ( k < n and arr [ i ] + arr [ j ] > arr [ k ] ) : NEW_LINE INDENT k += 1 NEW_LINE DEDENT if ( k > j ) : NEW_LINE INDENT count += k - j - 1 NEW_LINE DEDENT DEDENT DEDENT return count NEW_LINE DEDENT arr = [ 10 , 21 , 22 , 100 , 101 , 200 , 300 ] NEW_LINE print " Number ▁ of ▁ Triangles : " , findnumberofTriangles ( arr ) NEW_LINE